#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 q1_len; int q5_len[Q5_RUNS]; int q10_len[Q10_RUNS]; int q5_run; int q10_run; int update_max( int price, int coin, int max0[], int count ) { if (max[price] < max[price+coin*count]+count) { max[price] = max[price+coin*count] + count; max1[price] = max1[price+coin*count]; max5[price] = max5[price+coin*count]; max10[price] = max10[price+coin*count]; max25[price] = max25[price+coin]; max0[price] = max0[price+coin] + count; 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(&q1_len,0,sizeof(q1_len));; memset(q5_len,0,sizeof(q5_len)); memset(q10_len,0,sizeof(q10_len)); q5_run = q10_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,1)) 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,1)) 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,1)) 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,1)) 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,1)) q10[q10_run][q10_len[q10_run]++] = price; } /* 25cents */ price = P; if (!(price % 25) && (price/25) <= C4) update_max(0,25,max25,price/25); for (j = 0; j < 25 && j < q1_len; ++j ) { price = q1[q1_len-j-1]; if (!(price % 25) && (price/25) <= C4) update_max(0,25,max25,price/25); } for (k = 0; k < q5_run; ++k ) for (j = 0; j < 5 && j < q5_len[k]; ++j ) { price = q5[k][q5_len[k]-j-1]; if (!(price % 25) && (price/25) <= C4) update_max(0,25,max25,price/25); } for (k = 0; k < q10_run; ++k ) for (j = 0; j < 2 && j < q10_len[k]; ++j ) { price = q10[k][q10_len[k]-j-1]; if (!(price % 25) && (price/25) <= C4) update_max(0,25,max25,price/25); } 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; }