[Login|Register]
Problems

Status

Rank

Problem 1180
零钱
Time Limit: 1000ms
Memory Limit: 65536kb
Description
在超市里,最大的问题就是给钱和找钱。纸币类型有100,50,20,10, 5,1这么多的面值。为了完成一次固定数额的交易,例如你要买31元的物品,你可能给50元,这样对方要找回19(10+5+1+1+1+1)元,共要用7张纸币,或者你给51元,这样对方要找回20元,只要3张纸币。 所以你也会希望交易所需要用到的纸币数目尽可能地少,这样大家都方便了。
Input
多组测试数据,每组一行,每行是一个整数,表示要交易的金额。 交易金额不超过10000元。输入的金额为0的时候结束程序
Output
输出最少所需要的纸币数目
Sample Input
31
20
194
0
Sample Output
3
1
4
University of Science and Technology of China
Online Judge for ACM/ICPC
Processed in 0.9ms with 1 query(s).