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

Задача. В банкомате имеются в достаточном количестве купюры номиналом [latex]10, 20, 50, 100, 200[/latex] и [latex]500[/latex] гривен. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в [latex]n[/latex] гривен[latex](0 \leq n \leq 1000001)[/latex], или вывести [latex]-1[/latex], если указанную сумму выдать нельзя.

Тесты

Сумма 130 999 7360 3 80 123450 567 440
Число купюр 3 -1 18 -1 3 249 -1 4

 

Код программы:

Алгоритм

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

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

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Чтобы выяснить, так ли это, мы смотрим, что осталось от суммы после применения жадного»алгоритма. Если остаток равен [latex]0[/latex], то исходную сумму можно получить с помощью имеющихся купюр, и на экран выводится результат, полученный в цикле. Если же остаток больше [latex]0[/latex], такую операцию осуществить невозможно и программа выводит  [latex]-1[/latex].

 

Решение

Код программы

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

  1. Публиковать можно только задачи, которые получены Вами в качестве индивидуального задания от кого-то из преподавателей. В любом случае оно должно быть оформлены так, как описано здесь и обязательно должно содержать все перечисленные там элементы.
    Пожалуйста, доделайте это задание полностью и поставьте снова на проверку.

  2. Есть несколько замечаний:
    — Не нужно вставлять в коде программы пустые строки после каждой строки с текстом.
    — 1 ≤ n ≤ 1000000 это тоже формула, значит нужен latex
    -В разделе «Алгоритм» Вы не приводите ни обоснование правильности алгоритма, ни самого алгоритма. Например, последняя фраза «В конце программы проводится проверка на наличие остатка, меньшего 10» и соответствующий комментарий не соответствуют коду программы. Да, для данных значений элементов массива в конце в переменной n окажется остаток от деления на 10. Но 10 не является волшебным числом, волшебное число — минимальное значение элементов массива. Которое у Вас сейчас действительно 10 🙂
    Пожалуйста, разберитесь в чём именно состоит алгоритм, который Вы публикуете. Это так называемый жадный алгоритм. Он гораздо глубже и интереснее чем «цикл, в котором находит количество тех или иных купюр».

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