#include <stdio.h>
    /* greedy */
int nct;   /* number of coin type */
int vct[33], nc[33];    /* value of coin,  number of each coin */
int ncoins;  /* min. number of coins for the change */
void getCoinData(), printResult();
int ask(), makeChange(int);
int main(){
    int money, i;
    getCoinData();
    money=ask();
    while(money > 0){
        for(i=1; i<= nct; ++i) nc[i] = 0;  ncoins=0; /* clear */
        ncoins = makeChange(money);
        printResult();
        money=ask();
    }
    return 0;
}
void getCoinData(){
    int i, tmp[] = { 0, 1, 5, 10, 25, 50 };
    nct = sizeof(tmp) / sizeof(int) - 1;
    for(i=1; i<= nct; ++i) {
       vct[i] = tmp[i];
    }
}
int ask(){
    char tmp[99];
    printf("How much of the change? ");
    gets(tmp); 
    return (int)atol(tmp);
}
int makeChange(int m){
    int i, nthis;
    int nmin = 0;   /* number of min. coin */
    i = nct;   /* the max one */
    while(m){
        if(m >= vct[i]) {
            nthis = m / vct[i];
            nc[i] += nthis;
            nmin += nthis;
            m -= nthis * vct[i];   /* remain money */
        }
        --i;
    }
    return nmin;
}
void printResult(){
    int i;
    printf("Total number of coins required: %d\n", ncoins);
    for(i=nct; i>0; --i){
        if(nc[i]){
            printf("\t%d  x %2d\n", nc[i], vct[i]);
        }
    }
    printf("\n");
}