27 lines
793 B
Markdown
27 lines
793 B
Markdown
|
## Hit the Lottery
|
|||
|
|
|
|||
|
|
Allen has a LOT of money. He has 𝑛 dollars in the bank. For security reasons, he wants to withdraw it in cash (we will not disclose the reasons here). The denominations for dollar bills are **1**, **5**, **10**, **20**, **100**.
|
|||
|
|
|
|||
|
|
What is the minimum number of bills Allen could receive after withdrawing his entire balance?
|
|||
|
|
|
|||
|
|
### Input
|
|||
|
|
```
|
|||
|
|
125
|
|||
|
|
43
|
|||
|
|
1000000000
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### Output
|
|||
|
|
```
|
|||
|
|
3
|
|||
|
|
5
|
|||
|
|
10000000
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### Note
|
|||
|
|
|
|||
|
|
In the first sample case, Allen can withdraw this with a 100 dollar bill, a 20 dollar bill, and a 5 dollar bill. There is no way for Allen to receive 125 dollars in one or two bills.
|
|||
|
|
|
|||
|
|
In the second sample case, Allen can withdraw two 20 dollar bills and three 1 dollar bills.
|
|||
|
|
|
|||
|
|
In the third sample case, Allen can withdraw 100000000 (ten million!) 100 dollar bills.
|