#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 = 0; best[i].ch = ch; // test centu if (i >= 1) { if (best[i-1].ch.c1 > 0) { if (best[i-1].num + 1 > best[i].num) { best[i].num = best[i-1].num + 1; best[i].ch = best[i-1].ch; best[i].ch.c1 -= 1; } } } // test 5 if (i >= 5) { if (best[i-5].ch.c5 > 0) { if (best[i-5].num + 1 > best[i].num) { best[i].num = best[i-5].num + 1; best[i].ch = best[i-5].ch; best[i].ch.c5 -= 1; } } } // test 10 if (i >= 10) { if (best[i-10].ch.c10 > 0) { if (best[i-10].num + 1 > best[i].num) { best[i].num = best[i-10].num + 1; best[i].ch = best[i-10].ch; best[i].ch.c10 -= 1; } } } // test 25 if (i >= 25) { if (best[i-25].ch.c25 > 0) { if (best[i-25].num + 1 > best[i].num) { best[i].num = best[i-25].num + 1; best[i].ch = best[i-25].ch; best[i].ch.c25 -= 1; } } } //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; printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", c1, c5, c10, c25); } else printf("Charlie cannot buy coffee.\n"); } return 0; }