Minimum change P81629


Statement
 

pdf   zip

html

Write a program that, given an amount of euros and cents, computes the minimum number of banknotes and coins needed to get that amount. There are coins of 1, 2, 5, 10, 20 and 50 cents and of 1 and 2 euros, and banknotes of 5, 10, 20, 50, 100, 200 and 500 euros.

Input

Input consists of two natural numbers: the number of euros e and the number of cents c. Assume c<100.

Output

Print the number of banknotes and coins of each type that are are needed to represent the amount of the input, so as to minimize the total number of banknotes and coins.

Public test cases
  • Input

    9999 99
    

    Output

    Banknotes of 500 euros: 19
    Banknotes of 200 euros: 2
    Banknotes of 100 euros: 0
    Banknotes of 50 euros: 1
    Banknotes of 20 euros: 2
    Banknotes of 10 euros: 0
    Banknotes of 5 euros: 1
    Coins of 2 euros: 2
    Coins of 1 euro: 0
    Coins of 50 cents: 1
    Coins of 20 cents: 2
    Coins of 10 cents: 0
    Coins of 5 cents: 1
    Coins of 2 cents: 2
    Coins of 1 cent: 0
    
  • Input

    0 78
    

    Output

    Banknotes of 500 euros: 0
    Banknotes of 200 euros: 0
    Banknotes of 100 euros: 0
    Banknotes of 50 euros: 0
    Banknotes of 20 euros: 0
    Banknotes of 10 euros: 0
    Banknotes of 5 euros: 0
    Coins of 2 euros: 0
    Coins of 1 euro: 0
    Coins of 50 cents: 1
    Coins of 20 cents: 1
    Coins of 10 cents: 0
    Coins of 5 cents: 1
    Coins of 2 cents: 1
    Coins of 1 cent: 1
    
  • Input

    100 0
    

    Output

    Banknotes of 500 euros: 0
    Banknotes of 200 euros: 0
    Banknotes of 100 euros: 1
    Banknotes of 50 euros: 0
    Banknotes of 20 euros: 0
    Banknotes of 10 euros: 0
    Banknotes of 5 euros: 0
    Coins of 2 euros: 0
    Coins of 1 euro: 0
    Coins of 50 cents: 0
    Coins of 20 cents: 0
    Coins of 10 cents: 0
    Coins of 5 cents: 0
    Coins of 2 cents: 0
    Coins of 1 cent: 0
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++ Java Python
    User solutions
    C C++ Java Perl PHP Python