Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
2474. Попкорн
МоделированиеБинарный поиск
Олимпиадные задачи на русском языке
| 01/11/2019 | Муниципальный этап 9 класс (4) |
| 15/07/2020 | Лето 2020 - 7 (все) (G) |
| 31/10/2022 | «Базовая олимпиадная подготовка» (second level) - Бинарный поиск (проводит novink ) (G) |
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
"Мегамакс" проводит конкурс по поеданию попкорна на скорость. В конкурсе участвуют команды из `K` человек.
Для конкурса на столе выстраивается в линию `N` упаковок с попкорном, и каждый член команды берет несколько упаковок
подряд из линии, начиная слева. Можно брать любое количество упаковок, в том числе ни одной, если предыдущий член команды
забрал последнюю. Последний член команды забирает все оставшиеся упаковки. Нельзя меняться упаковками или нескольким
членам команды есть из одной упаковки. После распределения попкорна дается сигнал к старту, и все участники начинают есть
свой попкорн. Время завершения определяется по съевшему последний кусочек участнику и округляется вверх до целого числа секунд.
Количество попкорна в упаковках может быть разным, поэтому важно распределить упаковки среди участников команды так, чтобы
время поедания было минимальным. Известно, что человек может съесть ровно `S` кусочков попкорна в секунду.
Напишите программу, которая определяет минимальное время для поедания попкорна.
Первая строка ввода содержит три целых числа – количество упаковок попкорна `N` (`1\ ≤\ N\ ≤\ 10^5`), количество членов
команды `K` (`1\ ≤\ K\ ≤\ 10^5`) и скорость поедания попкорна `S` (`1\ ≤\ S\ ≤\ 50`) Следующая строка содержит `N` целых чисел – количество попкорна
в упаковках `P_i` (`1\ ≤\ P_i\ ≤\ 10^4`) слева направо.
Вывести одно целое число – минимальное время на поедание попкорна по правилам конкурса.
Пример ввода 1
5 3 4 5 8 3 10 7
Пример вывода 1
4
Пример ввода 2
3 2 1 1 5 1
Пример вывода 2
6
Система оценки и описание подзадач
Подзадача 1 (30 баллов)
`1\ ≤\ N\ ≤\ 20`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
Необходимые подзадачи: 1.
`20\ <\ N\ ≤\ 1000`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (40 баллов)
Необходимые подзадачи: 1,2.
`1000\ <\ N\ ≤\ 10^5`
В этой подзадаче 8 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.
