Cash Machine (Editorial)

Take a banknote of the maximum denomination $c$ available and use it to dispense the amount $n$ as long as possible. The maximum number of such banknotes that can be dispensed is $n/c$. The remainder $n\%с$ hryvnias are dispensed using other denominations.

Example

The amount of $770$ hryvnias can be dispensed as follows: 500 + 200 + 50 + 20.

Algorithm implementation

Store the denominations of available banknotes in the array $с$.

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

Read the input value of $n$.

scanf("%d", &n);

In the variable $res$ count the number of dispensed banknotes.

res = 0;

Iterate through the available six denominations of banknotes. To dispence the amount $n$, use a maximum of $n/c[i]$ banknotes with a denomination of $c[i]$. After using the denomination $c[i]$, the remaining amount is equal to $n\%c[i]$.

for (i = 0; i < 6; i++)
{
  res += n / c[i];
  n = n % c[i];
}

If the total sum is dispensed (n = 0), then print the found number of banknotes $res$. Otherwise print $-1$.

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

Java implementation

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 implementation

Read the input value of $n$.

n = int(input())

In the variable $res$ count the number of dispensed banknotes.

res = 0

Store the denominations of available banknotes in the list $с$.

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

Iterate through the available six denominations of banknotes. To dispence the amount $n$, use a maximum of $n/c[i]$ banknotes with a denomination of $c[i]$. After using the denomination $c[i]$, the remaining amount is equal to $n\%c[i]$.

for i in range(6):
  res += n // c[i]
  n %= c[i]

If the total sum is dispensed (n = 0), then print the found number of banknotes $res$. Otherwise print $-1$.

if n > 0:
  print("-1")
else:
  print(res)