НачалоПодразделы
Другие разделы
| 1577. Экономная маршрутизация |
| 1578. Последний урок |
| 1579. Самый тупой |
| 1581. Вирус 10.10.10 |
| 1582. Конфеты с десятичной точкой |
| 1583. Марсианская арифметика: декомпозиция |
| 1584. Матрёшки АТЭС |
Дата и время
22/12/2024 16:16:15
1580. Бутылка на всех
Бутылка на всех
Жадные алгоритмыКуча, очередь с приоритетами
Олимпиадные задачи на русском языке
| 04/07/2011 | Лето 2011 - дорешивание (02D) |
| 05/07/2011 | Лето 2011 - 2 (D) |
| 16/12/2015 | Занятие по теме "Жадные алгоритмы" (D) |
| 08/07/2019 | Лето 2019 - 4 (упрощенное) (A) |
| 02/12/2023 | Множества, словари (бонус) (проводит BOGAT) (C) |
Ограничения: время – 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
