|
Награждение участников олимпиады
(Время: 1 сек. Память: 32 Мб Сложность: 32%)
Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли A1 участников, второе место A2 участников, ..., заключительное N-е место заняли AN участников.
Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:
- Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
- Всем участникам, занявшим заключительное N-е место достанутся призы стоимостью в 1 денежную единицу;
- Разница D между призом участника на i-м месте и призом участника на i+1-м месте должна быть одинакова для всех i от 1 до N−1, в том числе, может быть и так, что D=0, то есть все участники могут получить одинаковые призы, независимо от занятого ими места.
Необходимо определить: какую максимальную разницу D жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы P.
Входные данные
В первой строке входного файла INPUT.TXT содержится одно натуральное число N − количество различных мест, которые заняли участники олимпиады (2 ≤ N ≤ 105). В следующих N строках, по одному в строке, находятся натуральные числа Ai − количество участников, занявших i-е место (i от 1 до N). Общее количество участников A1+A2+...+AN не превосходит 1018, любое Ai не менее 1. В последней строке находится натуральное число P − сумма, заложенная в смете на призы (P ≤ 1018). Гарантируется, что P ≥ A1+A2+...+AN, то есть для каждого участника можно купить приз стоимостью как минимум в одну денежную единицу.
Выходные данные
В выходной файл OUTPUT.TXT выведите одно неотрицательное целое число − максимальную разницу D, которую можно запланировать, не выходя за пределы суммы P.
Пример
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 5
2
1
3
4
2
100 | 4 |
Система оценки
Решения, правильно работающие для случаев, в которых P/N не превосходит 106, получат не менее 60 баллов.
Пояснение к примеру
В примере участники распределились следующим образом:
1 место − 2 участника,
2 место − 1 участник,
3 место − 3 участника,
4 место − 4 участника,
5 место − 2 участника.
Если заложить разницу между призами в 4 денежных единицы, то распределение стоимостей призов будет следующим:
5 место − 2 приза по 1 денежной единице,
4 место − 4 приза по 5 денежных единиц,
3 место − 3 приза по 9 денежных единиц,
2 место − 1 приз по 13 денежных единиц,
1 место − 2 приза по 17 денежных единиц.
Суммарно на призы будет потрачено 2*1+4*5+3*9+1*13+2*17 = 96 денежных единиц, что укладывается в смету в 100 денежных единиц. Если же заложить разницу между призами в 5 денежных единиц, то потребуется 2*1+4*6+3*11+1*16+2*21 = 117 денежных единиц, что превышает сумму, указанную в смете.
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| |
