买柿子

姜姜酱酱

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

#include <stdio.h>

int main(void)
{
        int c , d[500][6] , p[5] = {100 , 20 , 10 , 5 , 1} , i , j , k , s , t ;
        scanf("%d" , & t)                                                      ;
        for(i = 0 ; i < t ; i ++) scanf("%d" , & d[i][0])                      ;
        for(k = 0 ; k < t ; k ++) {
                for(i = 1 ; i < 6 ; i ++) d[k][i] = 0                          ;
                for(s = 0 , i = 1 ; i < 6 ; i ++) {
                        for(; s + p[i - 1] <= d[k][0] ;) {
                                s += p[i - 1]                                  ;
                                d[k][i] ++                                     ;
                        }
                }         
        }         
        for(k = 0 ; k < t ; k ++) {
                printf("%d = " , d[k][0])                                      ;
                for(c = 0 , i = 1 ; i < 6 ; i ++) {
                        if(d[k][0] < 1000) {
                                for(j = 0 ; j < d[k][i] ; j ++) {
                                        if(c) printf(" + ")                    ;
                                        printf("%d" , p[i - 1])                ;
                                        c ++                                   ;
                                }
                        } else {
                                if(d[k][i]) {
                                        if(c) printf(" + ")                    ;
                                        printf("%d * %d" , p[i - 1] , d[k][i]) ;
                                        c ++                                   ;
                                }
                        }
                }
                printf("\n")                                                   ;
        }
}

        编译、运行实况

D:\00.Excise\C>g++ -o x x.c

D:\00.Excise\C>x
5
99
101
137
188
199
99 = 20 + 20 + 20 + 20 + 10 + 5 + 1 + 1 + 1 + 1
101 = 100 + 1
137 = 100 + 20 + 10 + 5 + 1 + 1
188 = 100 + 20 + 20 + 20 + 20 + 5 + 1 + 1 + 1
199 = 100 + 20 + 20 + 20 + 20 + 10 + 5 + 1 + 1 + 1 + 1

D:\00.Excise\C>