Cash Change

Tough Dash, November 2022...
Limits 1s, 512 MB

You have an unlimited number of cash notes of the following denominations: 1, 5, 10, 50, 100, 500.

Given a number NN, determine the minimum number of cash notes required to make the total NN. For this problem, you will have to print out the values of each cash note in ascending order.

For example, when N=1535N = 1535, the minimum number of notes required is 7. And to make this total, you need the following cash notes:

5 10 10 10 500 500 500

Input

The input will contain a single integer NN (1N1041 \le N \le 10^4).

Output

Print the cash note values that in total make NN while requiring the minimum number of cash notes.

Sample

InputOutput
1535
5 10 10 10 500 500 500

Submit

Login to submit.

Statistics

91% Solution Ratio
spybitEarliest, 3w ago
CodeWith_IsmailFastest, 0.0s
Ultra.NazmulLightest, 5.7 MB
anonyo.akandShortest, 180B
Toph uses cookies. By continuing you agree to our Cookie Policy.