e-olymp 138. Банкомат

Ссылка на условие задания: e-olymp.

Условие

В банкомате имеются в достаточном количестве купюры номиналом $10$, $20$, $50$, $100$, $200$, $500$. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в $n$ гривен или вывести $-1$, если указанную сумму выдать нельзя.

Входные данные.

Одно число $n$ ([latex]1 \leq n \leq 1000000[/latex]).

Выходные данные.

Наименьшее количество купюр, которыми можно выдать $n$ гривен.

Тесты

Входные данные Выходные данные
Сумма Количество купюр
130 3
999 -1
7360 18
440 4
3 -1

Код.

Решение.

Для выполнения задания была написана функция, параметром для которой служит сумма, которую должен выдать автомат.
Сама функция является реализацией жадного алгоритма.Он заключается в том, чтобы взять купюру наибольшего достоинства, и найти, сколько раз она входит в данную сумму. То, что мы можем выдать только с помощью этой купюры, отнять от исходной суммы. Затем повторить операцию для оставшегося количества денег и самой большой из купюр меньшего достоинства. Перебрав таким образом все купюры, мы получим наименьшее их количество для получения данной суммы, что от нас, собственно, и требуется.

Такой алгоритм подходит не для всех валютных систем, а только для канонических — таких, в которых каждая купюра большего достоинства превышает меньшую более чем в два раза. В нашем случае это условие соблюдается.

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Для проверки этого условия, до начала выполнения жадного алгоритма, выполняется проверка. Если указанная сумма делится на 10 без остатка, то функция начинает выполнение алгоритма, если же нет, то возвращает $-1$.

Ссылка на решение задачи на сайте Try Haxe!

2 thoughts on “e-olymp 138. Банкомат

Добавить комментарий