#include <stdio.h>
/* Dynamic programming for stamps problem */
/* to minimize the number of stamps for the value. ノ程ぶ眎秎布 */
#define MAX_VALUE 999
#define UNIT_NAME "dollar"
#define VS_ARRAY  { 0, 1, 2, 5, 10, 25, 50, 100 }  /* 秎布肂 */
int nst;    /* number of stamp type */
int vs[33], ns[33];    /* value of stamp,  number of each stamp */
int nstamps;  /* min. number of stamps for the change */
void getStampData(), printResult(), prepareStamps();
int askUser(), makeChange(int);
int nmin[ MAX_VALUE+1 ];   /* min stamps for each i cents */
int left[MAX_VALUE+1] ,right[MAX_VALUE+1]; /* combination of money */
void countStamp(int);   /* 崩衡┮惠秎布计 */
void getStampData(){
    int tmp[] = VS_ARRAY;  /* 秎布肂 */
    int i;
    nst = sizeof(tmp) / sizeof(int) - 1;
    for(i=1; i<= nst; ++i) vs[i] = tmp[i];
}
/**********************************************************/
int main(){
    int money, i;
    getStampData();
    prepareStamps();
    money=askUser();
    while(money > 0  && money <= MAX_VALUE){
        nstamps = makeChange(money);
        for(i=1; i<= nst; ++i) ns[i] = 0;  /* clear stamp array */
        countStamp(money);   /* ns[]: count how many stamps for each stamp*/
        printResult();
        money=askUser();
    }
    return 0;
}
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 prepareStamps( ){ /* compute nmin[], left[], right[] */
    int i, k, m;
    nmin[0] = 0;   /* no stamp needed if no money */
    for(m=1; m<= MAX_VALUE; ++m) nmin[m] = MAX_VALUE;
    for(i=1; i <= nst; ++i)
        nmin[ vs[i] ] = 1;   /* these all need exactly one stamp */
    /******/
    for(m=2; m<= MAX_VALUE; ++m) {
       for(i=1; i< m; ++i) { 
          k = nmin[i] + nmin[m-i];
          if( k < nmin[m] ) {  /* k=╊Θ i 籔 m-i 琌ゑ耕ぶ秎布? */
             nmin[m] = k;     /* Yes. 癘程ぶ秎布计 */
             left[m] = i;    /* .. 癘琌パ i  籔 m-i 舱Θ */
             right[m] = m-i;
          }
       }/* for i */
    }
}
/**********************************************************/
void printResult(){
    int i;
    printf("Total number of stamps required: %d\n", nstamps);
    for(i=nst; i>0; --i){  /* 眖肂程蔼秨﹍ */
        if(ns[i]){  /* ぃ单 0  */
            printf("\t%2d  x %2d %s\n", ns[i], vs[i], UNIT_NAME);
        }
    }
    printf("\n");
}
void ncAdd(m){  /* m is the value of money */
    int i;     /* т ns[i] ぇ肂 m  i */
    for(i=1; i<=nst; ++i){
       if(m == vs[i]){
           ns[i]++;
           return;
       }
    }  /* т筂┮Τ秎布常⊿т玥ボΤ拜肈, ぃ赣祇ネ */
    printf("?something Wrong! %d ?\n", m);
}
void countStamp(int m){
    int i;
    if(nmin[m]==1) { ncAdd(m); return; }
    countStamp(left[m]);   /* m 琌パ left[m]  stamp  right[m]  */
    countStamp(right[m]);
}