Банкомат (Розбір)

Розглядаємо купюру максимального номіналу $с$ і використовуємо її для видачі суми $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)