07/04/2025 00:35:10

Рабочее место участника

Выбрать соревнование

Задачи

Послать решение

Результаты проверки

Статистика по задачам

Вопросы и ответы

Результаты соревнования

Задачи

1580. Бутылка на всех

Ограничения: время – 1s/2s, память – 128MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение 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

Пример ввода 2

4 3
0 101 5 12

Пример вывода 2

Источник: http://imcs.dvgu.ru/cats/ Школьники ACM, 2010

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)