Hit the Lottery

文章目录

一、Hit the Lottery

总结

一、Hit the Lottery

本题链接：Hit the Lottery

题目：

A. Hit the Lottery

time limit per test1 second

memory limit per test256 megabytes

inputstandard input

outputstandard output

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?

Input

The first and only line of input contains a single integer n (1≤n≤109).

Output

Output the minimum number of bills that Allen could receive.

Examples

input

125

output

3

input

43

output

5

input

1000000000

output

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.

本博客给出本题截图：

题意： 纸币有大有小，问最少可以用多少张纸币表示数字n

AC代码

#include <cstdio>
using namespace std;
int main()
{
    int a[5] = {1, 5, 10, 20, 100};
    int n;
    scanf("%d", &n);
    int res = 0;
    for (int i = 4; i >= 0; i -- )
    {
        int t = n / a[i];
        res += t;
        n -= a[i] * t;
    }
    printf("%d\n", res);
    return 0;
}

总结

水题，不解释