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






Этапы большого пути

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

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

Проект, выполняемый для одного из основных заказчиков фирмы "Фабрика классов", разбит на M этапов, на каждом из которых решается определенный круг задач. Руководство фирмы приняло решение проводить регулярную ротацию кадров, принимающих участие в разработке. Если на некотором этапе в разработке принимает участие N сотрудников фирмы, то не менее [N/3] из них (квадратными скобками обозначена целая часть числа N/3) не должны были участвовать в разработке на предыдущем этапе (на этапе, предыдущем к предыдущему эти сотрудники могли как участвовать, так и не участвовать в разработке).

Ваша задача - определить минимальное количество сотрудников, работающих в фирме "Фабрика классов", если известно, что решение руководства фирмы на каждом этапе может быть выполнено.

Формат входного файла input.txt

Первая строка - целое число M (2 <= M <= 1000) - количество этапов проекта

Вторая строка - M целых чисел через пробел (каждое не более 1000000) - количества сотрудников фирмы, которые принимают участие в работе над проектом на каждом из этапов.

Формат выходного файла output.txt

Первая строка - целое число C - минимально возможное количество сотрудников фирмы

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

6
11 2 8 12 7 4

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

14

Сдать задачу

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