Minimal change P92008


Statement
 

pdf   zip

thehtml

Write a program that, given a quantity of money expressed in euro cents, prints the minimal number of coins that you need to reach that quantity. You have an unlimited number of coins of each kind: 1 cents, 2 cents, 5 cents, 10 cents, 20 cents, 50 cents, 100 cents and 200 cents.

Input

The input is a sequence of naturals between 0 and 109, ended in -1. The sequence will not contain more than 10000 numbers.

Output

For each quantity of the input, that quantity has to be printed, followed by a colon, a space, and the minimal number of coins that you need to reach that quantity.

Public test cases
  • Input

    0
    1
    4
    6
    8
    89
    140
    666
    1000
    999
    -1
    

    Output

    0: 0
    1: 1
    4: 2
    6: 2
    8: 3
    89: 6
    140: 3
    666: 7
    1000: 5
    999: 11
    
  • Information
    Author
    Omer Giménez
    Language
    English
    Translator
    Carlos Molina
    Original language
    Spanish
    Other languages
    Spanish
    Official solutions
    C++
    User solutions
    C++ Java Python