Начало
Рабочее место участника
| Выбрать соревнование | Задачи | Послать решение | Результаты проверки | Статистика по задачам | Вопросы и ответы | Результаты соревнования | Состояние сервера | Изменить данные | Управление командой | Помощь |
Задачи
1580. Бутылка на всех
Жадные алгоритмыКуча, очередь с приоритетами
Олимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (02D) |
| 05/07/2011 | Лето 2011 - 2 (D) |
| 16/12/2015 | Занятие по теме "Жадные алгоритмы" (D) |
| 08/07/2019 | Лето 2019 - 4 (упрощенное) (A) |
| 14/10/2025 | Алгоритмы на деревьях ЧОМЛИ 11Б (проводит sartasova) (A) |
Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
После урока физкультуры `N` школьников собрались в магазине,
чтобы купить воды. Купив одну бутылку, они задумались:
ведь в бутылке всего `M` глотков воды, а денег на еще одну бутылку у них нет!
Чтобы использовать бутылку максимально эффективно,
школьники поступили следующим образом:
каждый из них назвал целое неотрицательное число,
показывающее, насколько сильно его мучает жажда.
Когда ученик делает глоток из бутылки, его жажда уменьшается ровно в десять раз
(с округлением вниз).
Необходимо определить, кто из жаждущих сколько глотков должен сделать,
чтобы, когда вода закончится, их суммарная жажда стала минимально возможной.
Входной файл содержит целые числа `N\ M` (`1\ ≤\ N,\ M\ ≤\ 10^5`),
за которыми следуют `N` чисел `a_i` (`0\ ≤\ a_i\ ≤\ 10^9`) – жажда `i`-го ученика.
Выходной файл должен содержать одно число –
минимально возможную суммарную жажду.
Пример ввода 1
2 3 9 30
Пример вывода 1
0
Пример ввода 2
4 3 0 101 5 12
Пример вывода 2
7
