Награждение участников олимпиады
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
— Мы все третье место заняли: и я, и Мишка, и Толька, и Кимка, все‑все. Вовка — первое, рыжий лягушонок — второе, а мы, остальные восемнадцать человек, мы заняли третье. Так инструктор сказал!
Виктор Драгунский, «Третье место в стиле баттерфляй».
Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли a1 участников, второе место — a2 участников, …, заключительное n‑е место заняли an участников.
Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:
1) Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
2) Всем участникам, занявшим заключительное n‑е место, достанутся призы стоимостью в 1 денежную единицу;
3) Разница d между призом участника на i‑м месте и призом участника на i+1‑м месте должна быть одинакова для всех i от 1 до n−1, в том числе может быть и так, что d=0, то есть все участники могут получить одинаковые призы независимо от занятого ими места.
Необходимо определить, какую максимальную разницу d жюри может запланировать при этих условиях, не выходя за пределы заложенной в смету суммы P.
Ответ
Для определения максимальной разницы d, которую жюри может запланировать при данных условиях, необходимо рассмотреть следующую логику:
1. Поскольку все участники, занявшие одно и то же место, должны получить одинаковые призы, число участников на каждом месте будет определяться количеством участников, занявших это место.
2. Призы для всех участников, занявших заключительное n-е место, должны стоить 1 денежную единицу каждый.
3. Разница d между призом участника на i-м месте и призом участника на i+1-м месте должна быть одинакова для всех i от 1 до n-1.
Для решения задачи можно использовать следующий алгоритм:
1. Найдите общее количество участников, занявших третье место (в данном случае 18 человек).
2. Вычислите количество участников на каждом месте, начиная с первого места. Для этого разделите общее количество участников на количество мест (в данном случае 1, 2 и 18).
3. Определите разницу d, вычитая приз последующего места из приза предыдущего места. В данном случае, разница d будет равна 1 (приз заключительного n-го места) минус приз второго места.
Жюри может запланировать максимальную разницу d в данном случае равную 1 денежной единице.