Городки
(Время: 1 сек. Память: 32 Мб Сложность: 28%)
Городки – старинная русская народная спортивная игра. В ней необходимо «выбивать» метанием биты различные деревянные фигуры, находящиеся на некотором расстоянии от игрока. Обычно участники самостоятельно приобретают комплекты для игры в спортивных магазинах, однако есть Очень Богатые Люди, готовые выложить за набор для игры из дорогих сортов древесины круглую сумму.
Начинающий предприниматель Тимофей заинтересовался этим перспективным бизнесом. Для организации официальных соревнований требуется изготовить для участников одинаковые биты, а для этого сначала необходимо где-то раздобыть как можно больше одинаковых деревянных палочек. В распоряжении Тимофея есть палочки-заготовки из дорогого красного дерева в форме цилиндров одинакового радиуса, но самой разной длины, из которых он и собирается изготовить биты.
Если длина палочки является чётным числом d, Тимофей может распилить её пополам и получить две палочки вдвое меньшей длины d/2. Если же длина палочки является нечётным числом, Тимофей может распилить её на две части, как можно меньше отличающиеся друг от друга: (d-1)/2 (d пополам, округлённое вниз до целой части) и (d+1)/2 (d пополам, округлённое вверх до целой части). Распиливать уже распиленные ранее палочки Тимофею лень, и он переходит к следующей заготовке. Задача Тимофея получить наибольшее количество бит какого-нибудь одного размера. Если таких размеров несколько, Тимофей выберет для организации соревнований наименьший.
Входные данные
В первой строке входного файла INPUT.TXT записано одно натуральное число: N (1 ≤ N ≤ 105) – длина самой длинной заготовки.
В следующих N строках записано по одному натуральному числу di (0 ≤ di ≤ 109, dN≠0) – количество палочек длины i-1 (здесь i – номер строки входных данных). Так, во второй строке записано количество палочек длины 1, в третьей – количество палочек длины 2 и так далее. В последней строке записано количество палочек длины N.
Выходные данные
В выходной файл OUTPUT.TXT выведите в двух строках два натуральных числа: наибольшее количество получившихся палочек одного размера и сам этот размер.
Пример
№ | INPUT.TXT | OUTPUT.TXT |
1 | 5 0 1 0 1 2 | 5 2 |
Система оценки
Решения, верно работающие при N ≤ 3, получат не менее 30 баллов.
Решения, верно работающие при N ≤ 1000, получат не менее 70 баллов.
Пояснение к примеру
У Тимофея есть несколько палочек, самая длинная имеет длину 5. Более точно:
- Нет палочек длины 1;
- Одна палочка длины 2;
- Нет палочек длины 3;
- Одна палочка длины 4;
- Две палочки длины 5.
Тимофей распилит пополам палочку длины 4 и получит две палочки длины 2. Также он распилит обе палочки длины 5 и получит две палочки длины 2 и две палочки длины 3. Вместе с имеющейся у него одной исходной палочкой длины 2 (её Тимофей пилить не будет) в его распоряжении окажется пять одинаковых палочек длины 2. Это наилучший результат, который может получить Тимофей (наибольшее количество палочек длины 1, которое можно получить из исходного набора, равно двум; палочек длины 3 двум; палочек длины 4 одному; палочек длины 5 двум).
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
|