买柿子

姜姜酱酱

Description

小西想向杂货商购买柿子，柿子一共需要多少​元，小西只有1、5、10、20、100元的硬币，请问他最少需要使用多少个硬币才能支付？


Input

输入多组数据，第一行是一个整数T表示数据组数。

接下来T组数据中，每组数据是一行一个整数n，表示需要支付的价钱。

1 <= T <= 10^6

1 <= n <= 10^9


Output

对于每组数据输出一行一个整数表示答案(需要硬币的个数)


Sample Input 1

3
125
43
1000000000
Sample Output 1

3
5
10000000
Hint

125=100+20+5

43=20+20+1+1+1

1000000000=100*10000000

jackz007

1. #include <stdio.h>
   
2. 
   
3. int main(void)
   
4. {
   
5.         int c , d[500][6] , p[5] = {100 , 20 , 10 , 5 , 1} , i , j , k , s , t ;
   
6.         scanf("%d" , & t)                                                      ;
   
7.         for(i = 0 ; i < t ; i ++) scanf("%d" , & d[i][0])                      ;
   
8.         for(k = 0 ; k < t ; k ++) {
   
9.                 for(i = 1 ; i < 6 ; i ++) d[k][i] = 0                          ;
   
10.                 for(s = 0 , i = 1 ; i < 6 ; i ++) {
    
11.                         for(; s + p[i - 1] <= d[k][0] ;) {
    
12.                                 s += p[i - 1]                                  ;
    
13.                                 d[k][i] ++                                     ;
    
14.                         }
    
15.                 }         
    
16.         }         
    
17.         for(k = 0 ; k < t ; k ++) {
    
18.                 printf("%d = " , d[k][0])                                      ;
    
19.                 for(c = 0 , i = 1 ; i < 6 ; i ++) {
    
20.                         if(d[k][0] < 1000) {
    
21.                                 for(j = 0 ; j < d[k][i] ; j ++) {
    
22.                                         if(c) printf(" + ")                    ;
    
23.                                         printf("%d" , p[i - 1])                ;
    
24.                                         c ++                                   ;
    
25.                                 }
    
26.                         } else {
    
27.                                 if(d[k][i]) {
    
28.                                         if(c) printf(" + ")                    ;
    
29.                                         printf("%d * %d" , p[i - 1] , d[k][i]) ;
    
30.                                         c ++                                   ;
    
31.                                 }
    
32.                         }
    
33.                 }
    
34.                 printf("\n")                                                   ;
    
35.         }
    
36. }

复制代码

        编译、运行实况

1. D:\00.Excise\C>g++ -o x x.c
   
2. 
   
3. D:\00.Excise\C>x
   
4. 5
   
5. 99
   
6. 101
   
7. 137
   
8. 188
   
9. 199
   
10. 99 = 20 + 20 + 20 + 20 + 10 + 5 + 1 + 1 + 1 + 1
    
11. 101 = 100 + 1
    
12. 137 = 100 + 20 + 10 + 5 + 1 + 1
    
13. 188 = 100 + 20 + 20 + 20 + 20 + 5 + 1 + 1 + 1
    
14. 199 = 100 + 20 + 20 + 20 + 20 + 10 + 5 + 1 + 1 + 1 + 1
    
15. 
    
16. D:\00.Excise\C>

复制代码