[Home|Training|Problems|Contests|C Language] | [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 |