#include #include #include #include struct change { int c1, c5, c10, c25; change(int x1, int x5, int x10, int x25) : c1(x1), c5(x5), c10(x10), c25(x25) {} change() : c1(0), c5(0), c10(0), c25(0) {} void print() { printf("[%d %d %d %d]\n", c1, c5, c10, c25); } }; struct elem { int num; change ch; elem(int _num, const change& _ch) : num(_num), ch(_ch) {} elem() : num(0) {} void print() { printf("%d [%d %d %d %d]\n", num, ch.c1, ch.c5, ch.c10, ch.c25); } }; elem best[10001]; int main() { for(;;) { int P; change ch; scanf("%d %d %d %d %d", &P, &ch.c1, &ch.c5, &ch.c10, &ch.c25); if (P == 0) break; best[0] = elem(0, ch); //best[0].print(); for (int i = 1; i <= P; ++i) { best[i].num = -1; best[i].ch = ch; // test centu for (int j = 1; (j <= 1) && (1 * j <= i); ++j) { int k = i - 1 * j; if ((best[k].ch.c1 >= j) && best[k].num >= 0) { if (best[k].num + j > best[i].num) { best[i].num = best[k].num + j; best[i].ch = best[k].ch; best[i].ch.c1 -= j; } } } // test 5 for (int j = 1; j <= 1 && 5 * j <= i; ++j) { int k = i - 5 * j; if (best[k].ch.c5 >= j && best[k].num >= 0) { if (best[k].num + j > best[i].num) { best[i].num = best[k].num + j; best[i].ch = best[k].ch; best[i].ch.c5 -= j; } } } // test 10 for (int j = 1; j <= 1 && 10 * j <= i; ++j) { int k = i - 10 * j; if (best[k].ch.c10 >= j && best[k].num >= 0) { if (best[k].num + j > best[i].num) { best[i].num = best[k].num + j; best[i].ch = best[k].ch; best[i].ch.c10 -= j; } } } // test 25 for (int j = 1; j <= 1 && 25 * j <= i; ++j) { int k = i - 25 * j; if (best[k].ch.c25 >= j && best[k].num >= 0) { if (best[k].num + j > best[i].num) { best[i].num = best[k].num + j; best[i].ch = best[k].ch; best[i].ch.c25 -= j; } } } //best[i].print(); } if (best[P].num > 0) { int c1 = best[0].ch.c1 - best[P].ch.c1; int c5 = best[0].ch.c5 - best[P].ch.c5; int c10 = best[0].ch.c10 - best[P].ch.c10; int c25 = best[0].ch.c25 - best[P].ch.c25; if (c1 + 5*c5 + 10*c10 + 25*c25 == P) printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", c1, c5, c10, c25); else printf("Charlie cannot buy coffee.\n"); } else printf("Charlie cannot buy coffee.\n"); } return 0; }