#include #include #include #include #include #define MAX 10005 #define Q5_RUNS 6 #define Q10_RUNS 21 int max[MAX]; int max1[MAX],max5[MAX],max10[MAX],max25[MAX]; int q1[MAX]; int q5[Q5_RUNS][MAX]; int q10[Q10_RUNS][MAX]; /* int q25[150][MAX]; */ int q1_len; int q5_len[Q5_RUNS]; int q10_len[Q10_RUNS]; /* int q25_len[150]; */ int q5_run; int q10_run; /* int q25_run; */ int update_max( int price, int coin, int max0[] ) { if (max[price] < max[price+coin]+1) { max[price] = max[price+coin] + 1; max1[price] = max1[price+coin]; max5[price] = max5[price+coin]; max10[price] = max10[price+coin]; max25[price] = max25[price+coin]; max0[price] = max0[price+coin] + 1; return 1; } return 0; } int main(void) { int C1, C2, C3, C4, P; int i, j, k, price; while(1) { scanf("%d %d %d %d %d\n", &P, &C1, &C2, &C3, &C4 ); if (!P) break; memset(max,0,sizeof(max)); memset(max1,0,sizeof(max1)); memset(max5,0,sizeof(max5)); memset(max10,0,sizeof(max10)); memset(max25,0,sizeof(max25)); memset(q1,0,sizeof(q1)); memset(q5,0,sizeof(q5)); memset(q10,0,sizeof(q10)); /* memset(q25,0,sizeof(q25)); */ memset(&q1_len,0,sizeof(q1_len));; memset(q5_len,0,sizeof(q5_len)); memset(q10_len,0,sizeof(q10_len)); /* memset(q25_len,0,sizeof(q25_len)); */ q5_run = q10_run /* = q25_run*/ = 0; /* cents */ for ( i = 0; i < C1; ++i ) { q1[i] = P-1-i; max1[P-1-i] = max[P-1-i] = i+1; } q1_len = C1; /* 5cents */ q5_run = 0; price = P-5; for ( i = 0; i < C2 && price >= 0; ++i, price -= 5 ) if (update_max(price,5,max5)) q5[q5_run][q5_len[q5_run]++] = price; ++q5_run; for (j = 0; j < 5 && j < q1_len; ++j, ++q5_run ) { price = q1[q1_len-j-1] - 5; for ( i = 0; i < C2 && price >= 0; ++i, price -= 5 ) if (update_max(price,5,max5)) q5[q5_run][q5_len[q5_run]++] = price; } /* 10cents */ q10_run = 0; price = P-10; for ( i = 0; i < C3 && price >= 0; ++i, price -= 10 ) if (update_max(price,10,max10)) q10[q10_run][q10_len[q10_run]++] = price; ++q10_run; for (j = 0; j < 10 && j < q1_len; ++j, ++q10_run ) { price = q1[q1_len-j-1] - 10; for ( i = 0; i < C3 && price >= 0; ++i, price -= 10 ) if (update_max(price,10,max10)) q10[q10_run][q10_len[q10_run]++] = price; } for (k = 0; k < q5_run; ++k ) for (j = 0; j < 2 && j < q5_len[k]; ++j, ++q10_run ) { price = q5[k][q5_len[k]-j-1] - 10; for ( i = 0; i < C3 && price >= 0; ++i, price -= 10 ) if (update_max(price,10,max10)) q10[q10_run][q10_len[q10_run]++] = price; } /* 25cents */ /* q25_run = 0; */ price = P-25; for ( i = 0; i < C4 && price >= 0; ++i, price -= 25 ) if (update_max(price,25,max25)) ;/*q25[q25_run][q25_len[q25_run]++] = price;*/ /* ++q25_run; */ for (j = 0; j < 25 && j < q1_len; ++j/*, ++q25_run*/ ) { price = q1[q1_len-j-1] - 25; for ( i = 0; i < C4 && price >= 0; ++i, price -= 25 ) if (update_max(price,25,max25)) ;/* q25[q25_run][q25_len[q25_run]++] = price; */ } for (k = 0; k < q5_run; ++k ) for (j = 0; j < 5 && j < q5_len[k]; ++j/*, ++q25_run*/ ) { price = q5[k][q5_len[k]-j-1] - 25; for ( i = 0; i < C4 && price >= 0; ++i, price -= 25 ) if (update_max(price,25,max25)) ;/*q25[q25_run][q25_len[q25_run]++] = price;*/ } for (k = 0; k < Q10_RUNS; ++k ) for (j = 0; j < 2 && j < q10_len[k]; ++j/*, ++q25_run*/ ) { price = q10[k][q10_len[k]-j-1] - 10; for ( i = 0; i < C4 && price >= 0; ++i, price -= 25 ) if (update_max(price,25,max25)) ;/*q25[q25_run][q25_len[q25_run]++] = price;*/ } if (max[0]) printf("Throw in %d cents, %d nickels, %d dimes, %d quarters.\n", max1[0],max5[0],max10[0],max25[0] ); else puts("Charlie cannot buy coffee."); } return 0; }