#include #define MAXP 10047 const int H[4] = {1,5,10,25}; int R[4],C[4]; int A[MAXP]; int B[MAXP][4]; int D[MAXP]; int P; int S[MAXP]; int S2[MAXP]; int head; void push(int X) { head++; S[head]=X; } int pop() { int t = S[head]; S[head]=0; head--; return t; } void print() { int i,j; for(i=0;i<=P;i++) printf("%d ",A[i]); printf("\n"); for(i=0;i<=P;i++) printf("%d ",D[i]); printf("\n"); for(i=1;i<=head;i++) printf("%d ",S[i]); printf("\n"); printf("\n"); for(j=0;j<4;j++) { for(i=0;i<=P;i++) printf("%d ",B[i][j]); printf("\n"); } printf("---------------------------\n"); } int main() { int i,j,k,q,ci,d; int check,last,start; while (1) { scanf("%d %d %d %d %d\n",&P,&(C[0]),&(C[1]),&(C[2]),&(C[3])); if (P == 0) break; for(j=0;j<4;j++) for(i=0;i<=P;i++) { B[i][j]=0; } for(i=0;i<=P;i++) { D[i]=0; A[i]=0; } for(j=0;j<4;j++) { if (C[j]>(P / H[j])) C[j] = (P / H[j]); } A[0]=1; for(j=0; j<4; j++) { /* init stack */ head=0; q=H[j]; for(i=0;i<=P-q;i++) if (A[i]==1) push(i); /* printf("*****************************\n"); print(); printf("*****************************\n"); */ for(ci=0; ci 0) { i=pop(); if ( (A[i+q]==0) || (D[i+q]=0;i--) push(S2[i]); /* print(); */ } } if (A[P]==0) { printf("Charlie cannot buy coffee.\n"); } else { printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",B[P][0],B[P][1],B[P][2],B[P][3]); } } return 0; }