Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Курсы ККДП
Дистрибутивы
Статьи
Ссылки


 

Награждение участников олимпиады

(Время: 1 сек. Память: 32 Мб Сложность: 32%)

Жюри подводит итоги очередной олимпиады по информатике. В этот раз получилось так, что многие участники набрали одинаковое число баллов. Согласно окончательной таблице результатов, первое место заняли A1 участников, второе место A2 участников, ..., заключительное N-е место заняли AN участников.

Согласно регламенту соревнования, требуется каждого участника наградить призом. Суммарно на все призы в смете олимпиады заложена сумма в P денежных единиц. Жюри хочет, чтобы при покупке призов выполнялись следующие условия:

  1. Всем участникам, занявшим одно и то же место, достанутся одинаковые призы;
  2. Всем участникам, занявшим заключительное N-е место достанутся призы стоимостью в 1 денежную единицу;
  3. Разница 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.TXTOUTPUT.TXT
15
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 денежных единиц, что превышает сумму, указанную в смете.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]


 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Школьный этап
 Муниципальный этап
 Региональный этап
 Полуфинал ВКОШП
 Личное первенство СФУ
 2007 / 2008 1 тур
 2007 / 2008 2 тур
 2007 / 2008 3 тур
 2008 / 2009 1 тур
 2008 / 2009 2 тур
 2008 / 2009 3 тур
 2009 / 2010 1 тур
 2009 / 2010 2 тур
 2009 / 2010 3 тур
 2010 / 2011 1 тур
 2010 / 2011 2 тур
 2010 / 2011 3 тур
 2011 / 2012 1 тур
 2011 / 2012 2 тур
 2011 / 2012 3 тур
 2012 / 2013 1 тур
 2012 / 2013 2 тур
 2012 / 2013 3 тур
 2013 / 2014 7-8 классы
 2013 / 2014 9-11 классы
 2014 / 2015 7-8 классы
 2014 / 2015 9-11 классы
 2015 / 2016 7-8 классы
 2015 / 2016 9-11 классы
 2016 / 2017 7-8 классы
 2016 / 2017 9-11 классы
 2017 / 2018 7-8 классы
 2017 / 2018 9-11 классы
 2018 / 2019 7-8 классы
 2018 / 2019 9-11 классы
 2019 / 2020 7-8 классы
 2019 / 2020 9-11 классы
 2020 / 2021 7-8 классы
 2020 / 2021 9-11 классы
 2021 / 2022 7-8 классы
 2021 / 2022 9-11 классы
 2022 / 2023
 2023 / 2024
 2024 / 2025
 A. Прямые и окружности
 B. Братья и сёстры
 C. Шестёрки
 D. Награждение участников олимпиады
 E. Фермер Джон и древний камень

Красноярский краевой Дворец пионеров, (c)2006 - 2025, ИНН 246305493507, E-mail: admin@acmp.ru