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]

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)