Условие задачи

Есть купюры и монеты номиналами: 1 5 10 50 100 1000 5000 рублей. В банкомате неограниченное количество купюр каждого номинала. Александр хочет снять со счёта $N$ рублей. Нужно определить минимальное суммарное количество купюр и монет, которое может выдать банкомат, чтобы получить сумму $N$.

---

Решение

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

---

Сложность

Сложность алгоритма - $O(n)$, где $n$ количество номиналов.

---

Псевдокод

Аннотация:
N - сумма денег, которую нужно выдать

Функция_выдачи_денег(N)
    номиналы = [1, 5, 10, 50, 100, 1000, 5000]  
    счётчик <- 0
    
    для i в номиналах, начиная с бОльших
        счётчик <- счётчик + (N div i)
        N <- N mod i
        
    вернуть счётчик 

---

Реализация на Python

Аннотация:
cash_dispenser - функция для вычисления минимального количества купюр для заданной суммы
N - сумма денег, которую нужно выдать
nominals - список доступных номиналов купюр, отсортированный в порядке возрастания
count - переменная для хранения количества купюр

def cash_dispenser(N):  
    nominals = [5000, 1000, 100, 50, 10, 5, 1]  
    count = 0 
     
    for i in nominals:  
        count += N // i  
        N %= i  
        
    return count

---

Олимпиадная реализация на C++

Аннотация:
cash_dispenser - функция для вычисления минимального количества купюр для заданной суммы
N - сумма денег, которую нужно выдать
nominals - вектор доступных номиналов купюр, отсортированный в порядке убывания
c - переменная для хранения количества купюр

int cash_dispenser(int N) {
    vector<int> nominals = {5000, 1000, 100, 50, 10, 5, 1};
    int c = 0;
    
    for (int i : nominals) {
        c += N / i;
        N %= i;
    }
    
    return count;
}

---

Продуктовая реализация на C++

Аннотация:
cash_dispenser - функция для вычисления минимального количества купюр для заданной суммы
amount_issued - сумма денег, которую нужно выдать
nominals_banknots - вектор доступных номиналов купюр отсортированный в порядке убывания
count_banknots - переменная для хранения количества купюр

int cash_dispenser(int amount_issued) {
    vector<int> nominals_banknots = {5000, 1000, 100, 50, 10, 5, 1};
    int count_banknots = 0;
    
    for (int nominal : nominals_banknots) {
        count_banknots += amount_issued / nominal;
        amount_issued %= nominal;
    }
    
    return count_banknots;
}