#include <stdio.h>
/* making change --- Dynamic programming version, ver.1 */
int nct;   /* number of coin type */
int vc[33], nc[33];    /* value of coin,  number of each coin */
int ncoins;  /* min. number of coins for the change */
void getCoinData(), printResult();
int askUser(), makeChange(int);
int nmin[100];   /* min coins for each i cents */
int imax=0;
int main(){
    int money, i;
    getCoinData();
    money=askUser();
    while(money > 0){
        imax=0;
        for(i=1; i<=money; ++i) nmin[i] = money;
        for(i=1; i<= nct; ++i) nc[i] = 0;  ncoins=0; /* clear */
        ncoins = makeChange(money);
        printResult();
        money=askUser();
    }
    return 0;
}
void getCoinData(){
    int i, tmp[] = { 0, 1, 5, 10, 21, 50 };
    nct = sizeof(tmp) / sizeof(int) - 1;
    for(i=1; i<= nct; ++i) {
       vc[i] = tmp[i];
    }
}
int askUser(){
    static char tmp[99];
    printf("How much of the change? ");
    gets(tmp); 
    return (int)atol(tmp);
}
int makeChange(int m){
    int i, k;
    for(i=1; i <= nct; ++i){
       if(m == vc[i]) return 1;
    }
    if(m <= imax) return nmin[m];   /* Remove this line and try again ! */
    for(i=1; i< m; ++i) {
       k = makeChange(i) + makeChange(m-i);
       if( k < nmin[m] ) nmin[m] = k;
       if(i>imax) imax = i;
    }
    return nmin[m];
}
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], vc[i]);
        }
    }
    printf("\n");
}