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

Беремо купюру максимального номіналу $с$ і використовуємо її для видачі суми $n$ поки це можливо. Максимум таких купюр можна видати $n/c$ штук. Залишок $n\%c$ гривень видаємо іншими номіналами.

Приклад

Суму в 770 гривень можна видати наступним чином: 500 + 200 + 50 + 20.

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

Номінали наявних купюр занесемо в масив $c$.

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$.

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)