Hide
Problem E
Exact Change
Photo by Jason
Leung on Unsplash
Jayden is a student at Mines, and this semester he wants to study abroad in a foreign country called Umbertoland. In addition to their language and culture, Umbertoland also has a unique currency system. The bill denominations are as follows:
-
$1$ dollar
-
$5$ dollars
-
$15$ dollars
-
$30$ dollars
-
$150$ dollars
Given the price of an item, help Jayden figure out how many of each bill to use in order to pay the exact amount using the fewest bills possible.
Input
The input will consist of one integer $0 \leq N \leq 1\, 000$ which is the price of the item in dollars.
Output
Print five space-seperated integers, the number of $$1$, $$5$, $$15$, $$30$, and $$150$ bills needed to pay with the fewest total bills, respectively.
| Sample Input 1 | Sample Output 1 |
|---|---|
16 |
1 0 1 0 0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
44 |
4 2 0 1 0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
45 |
0 0 1 1 0 |
