Супер-Пупер-Банкомат
Очень простая
Ограничение по времени выполнения 1 секунда
Ограничение по использованию памяти 64 мегабайта
В обращении находятся банкноты номиналами 1, 2, 5, 10, 20, 50, 100, 200 и 500 гривен. В Супер-Пупер-Банкомате имеется в наличии большое количество каждой из этих банкнот. Какое минимальное количество банкнот банкомат может выдать для суммы S?
Входные данные
Одно целое число S, где 1 ≤ S ≤ 12345.
Выходные данные
Одно целое число — минимальное количество банкнот, которыми можно выдать указанную сумму.
Примеры
Ввод #1
Ответ #1
Примечание
Сумму 2018 можно выдать как 500+500+500+500+10+5+2+1, то есть восемью банкнотами. Меньшим количеством банкнот указанных номиналов выдать сумму 2018 невозможно.
Отправки 2K
Коэффициент принятия 51 %