#include <stdio.h>
#define MAX_CHANGE 99
/* making change --- Dynamic programming version, ver.2 */
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(), prepareChange();
int askUser(), makeChange(int);
int nmin[ MAX_CHANGE+1 ];   /* min coins for each i cents */
int imax=0;
int main(){
    int money, i;
    getCoinData();
    prepareChange();
    money=askUser();
    while(money > 0){
        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? ");
    fgets(tmp, 99, stdin); 
    return (int)atol(tmp);
}
int makeChange(int m){
    return nmin[m];
}
void prepareChange( ){
    int i, k, m;
    nmin[0] = 0;
    for(m=1; m<= MAX_CHANGE; ++m) nmin[m] = MAX_CHANGE;
    for(i=1; i <= nct; ++i)
        nmin[ vc[i] ] = 1;   /* exactly one coin */
    /******/
    for(m=2; m<= MAX_CHANGE; ++m) {
       for(i=1; i< m; ++i) {
          k = nmin[i] + nmin[m-i];
          if( k < nmin[m] ) nmin[m] = k;
       }
    }
}
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");
}