138. Банкомат

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

Вход. Одно число n (1 ≤ n ≤ 10⁶).

Выход. Выведите наименьшее количество купюр, которыми можно выдать n гривен. Выведите -1, если указанную сумму выдать нельзя.

Пример входа	Пример выхода
770	4

РЕШЕНИЕ

жадный алгоритм

Анализ алгоритма

Берем купюру максимального номинала с и используем ее для выдачи суммы n пока это возможно. Максимум таких купюр можно выдать n / с штук. Остаток n % с гривен выдаем остальными номиналами.

Пример

Сумму в 770 гривен можно выдать следующим образом: 500 + 200 + 50 + 20.

Реализация алгоритма

Номиналы имеющихся купюр занесем в массив с.

int c[6] = { 500, 200, 100, 50, 20, 10 };

Читаем входную сумму n.

scanf("%d", &n);

В переменной res подсчитываем количество выданных купюр.

res = 0;

Перебираем имеющиеся в наличии шесть номиналов купюр. Для выдачи суммы n можно использовать максимум n / c[i] купюр номиналом c[i]. После использования номинала c[i] оставшаяся сумма равна n % c[i].

for (i = 0; i < 6; i++)

{

res += n / c[i];

n = n % c[i];

}

Если вся сумма выдана (n = 0), то выводим найденное количество купюр res. Иначе выводим -1.

if (n > 0) printf("-1\n"); else printf("%d\n", res);

Java реализация

import java.util.*;

public class Main

{

static int c[] = {500, 200, 100, 50, 20, 10};

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int res = 0;

for(int i = 0; i < 6; i++)

{

res += n / c[i];

n = n % c[i];

}

if (n > 0)

System.out.println("-1");

else

System.out.println(res);

con.close();

}

}

Python реализация

Читаем входную сумму n.

n = int(input())

В переменной res подсчитываем количество выданных купюр.

res = 0

Номиналы имеющихся купюр занесем в список с.

c = [500, 200, 100, 50, 20, 10]

Перебираем имеющиеся в наличии шесть номиналов купюр. Для выдачи суммы n можно использовать максимум n / c[i] купюр номиналом c[i]. После использования номинала c[i] оставшаяся сумма равна n % c[i].

for i in range(6):

res += n // c[i]

n %= c[i]

Если вся сумма выдана (n = 0), то выводим найденное количество купюр res. Иначе выводим -1.

if n > 0:

print("-1")

else:

print(res)