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