Hit the Lottery
题意翻译
给出一个数 $n$,
令 $n = k_1 + k_2 * 5 + k_3 * 10 + k_4 * 20 + k_5 * 100, k \epsilon N^*$
最小化$Answer = \sum_{i = 1} ^ {5} k_i$
感谢@wsndy 提供的翻译
题目描述
Allen has a LOT of money. He has $ n $ 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?
输入输出格式
输入格式
The first and only line of input contains a single integer $ n $ ( $ 1 \le n \le 10^9 $ ).
输出格式
Output the minimum number of bills that Allen could receive.
输入输出样例
输入样例 #1
125
输出样例 #1
3
输入样例 #2
43
输出样例 #2
5
输入样例 #3
1000000000
输出样例 #3
10000000
说明
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.