Question

Банкомат. В банкомате имеются в достаточном количестве купюры номиналом 50, 100, 200, 500 и 1000 рублей. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в n рублей или вывести -1, если указанную сумму выдать нельзя. Входные данные. Одно число n (1 ≤ n ≤ 106). Выходные данные. Вывести наименьшее количество купюр, которыми можно выдать n рублей. ​

Answer 1

Программа:

C++:

#include <iostream>

using namespace std;

int main()

{

   int BILL[] = { 1000, 500, 200, 100, 50 };

   int n, j, k;

   cin >> n;

   k = 0;

   

   for (int i = 0; i < 5; ++i) {

       j = BILL[i];

       k += n / j;

       n %= j;

   }

   

   if (n > 0) { k = -1; }

   

   cout << k;

}

Answer 2

Для решения этой задачи можно использовать жадный алгоритм.

1. Создаем переменную "количество купюр" и устанавливаем ее равной 0. 2. Пока n больше 0: - Если n больше или равно 1000, вычитаем из n 1000 и увеличиваем количество купюр на 1. - Иначе, если n больше или равно 500, вычитаем из n 500 и увеличиваем количество купюр на 1. - Иначе, если n больше или равно 200, вычитаем из n 200 и увеличиваем количество купюр на 1. - Иначе, если n больше или равно 100, вычитаем из n 100 и увеличиваем количество купюр на 1. - Иначе, если n больше или равно 50, вычитаем из n 50 и увеличиваем количество купюр на 1. - Иначе, если n меньше 50 и не равно 0, выводим -1, так как указанную сумму невозможно выдать. 3. Выводим количество купюр.

Пример реализации на языке Python:

n = int(input("Введите сумму: "))
count = 0

while n > 0:
    if n >= 1000:
        n -= 1000
        count += 1
    elif n >= 500:
        n -= 500
        count += 1
    elif n >= 200:
        n -= 200
        count += 1
    elif n >= 100:
        n -= 100
        count += 1
    elif n >= 50:
        n -= 50
        count += 1
    else:
        print(-1)
        break

if n == 0:
    print(count)

Например, если вводимая сумма равна 1378, программа выведет 9, что означает, что минимальное количество купюр для выдачи этой суммы составляет 9 штук (1 купюра номиналом 1000 рублей, 1 купюра номиналом 200 рублей, 3 купюры номиналом 50 рублей и 4 купюры номиналом 10 рублей). Если указанную сумму невозможно выдать, программа выведет -1.