#include #include #define MAXP 10240 int main(void) { for (;;) { static unsigned max[MAXP], m1[MAXP], m5[MAXP], m10[MAXP], m25[MAXP]; static char pos[MAXP]; unsigned p, c1, c5, c10, c25; size_t i; scanf ("%u%u%u%u%u", &p, &c1, &c5, &c10, &c25); if (p == 0) break; memset (pos, 0, (p + 1) * sizeof (*pos)); memset (max, 0, (p + 1) * sizeof (*max)); memset (m1, 0, (p + 1) * sizeof (*m1)); memset (m5, 0, (p + 1) * sizeof (*m5)); memset (m10, 0, (p + 1) * sizeof (*m10)); memset (m25, 0, (p + 1) * sizeof (*m25)); pos[0] = 1; for (i = 1; i <= c1; i++) { max[i] = 1; m1[i] = i; pos[i] = 1; } #define TRY(VAL) \ for (i = p; i >= VAL; i--) \ { \ size_t j; \ \ for (j = 1; j <= c##VAL; j++) \ { \ unsigned v; \ size_t p; \ \ if (i < VAL * j) \ break; \ p = i - VAL * j; \ v = max[p] + j; \ if (pos[p] != 0 && max[i] < v) \ { \ pos[i] = 1; \ \ max[i] = v; \ m1[i] = m1[p]; \ m5[i] = m5[p]; \ m10[i] = m10[p]; \ m25[i] = m25[p]; \ m##VAL[i] += j; \ } \ if (p < VAL) \ break; \ } \ } TRY (5); TRY (10); TRY (25); if (max[p] == 0) printf ("Charlie cannot buy coffee.\n"); else printf ("Throw in %u cents, %u nickels, %u dimes, and %u quarters.\n", m1[p], m5[p], m10[p], m25[p]); } return EXIT_SUCCESS; }