Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 

... и шитья

Задачу добавил: alef

Успешно сдано решений: 31

Время на тест - 1 с

Когда скатерть была разрезана на салфетки, в залу вновь вошли двое в темно-синих плащах, что-то вновь сказали человечку, затем уложили салфетки в стопки и унесли их.
Человечек подошел к друзьям и объявил им:
- Великий маг доволен, что вы справились с заданием. Но он просит вас сделать еще кое-что...
Следующее задание Ормуса состояло в том, чтобы сшить оставшиеся разноцветные квадраты в тесьму - шириной в один квадрат и максимально возможной длины. Однако квадраты одного цвета не должны соприкасаться друг с другом сторонами. Кроме того, тесьма должна начинаться и заканчиваться квадратами разного цвета.
Ваша задача - по заданному набору квадратов определить максимально возможную длину тесьмы.

Формат входного файла input.txt
Первая строка - целое число K (1 <= K <= 10) - количество наборов квадратов
Затем следует K блоков описаний квадратов
Первая строка блока - целое число C (1 <= C <= 20) - количество различных цветов
Вторая строка блока содержит C целых чисел S1, S2, ..., SC через пробел. Число Sj (j = 1, 2, ..., C) - количество квадратов цвета j

Формат выходного файла output.txt
В каждой из K строк содержится  по одному числу - максимальной длине тесьмы, которая может получиться из квадратов согласно условию задачи.

Пример входного файла
1
2
20 1

Пример выходного файла
2

Сдать задачу

Задать вопрос жюри по этой задаче