#include #define MAXN 1047 const int H[4] = {1,5,10,25}; int R[4],C[4]; int A[MAXN][4]; int B[MAXN][4]; int P; int main() { int i,j,k,q; 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++) { A[i][j]=0; B[i][j]=0; } A[0][0]=1; for(i=1; i<=C[0]; i++) { A[i][0]=1; B[i][0]=i; } for(j=1; j<4; j++) { for( i=0; i<=P; i++ ) A[i][j]=A[i][j-1]; for( i=(P-H[j]); i>=0; i-- ) if (A[i][j-1]==1) { A[i][j]=1; k=1; q=H[j]; while( (k<=C[j]) && ((i+k*q)<=P) && (A[i+k*q][j]==0) ) { A[i+k*q][j]=1; B[i+k*q][j]=k; k++; } } } /* for(j=0;j<3;j++) { for(i=0;i<=P;i++) printf("%d ",A[i][j]); printf("\n"); } printf("\n"); for(j=0;j<3;j++) { for(i=0;i<=P;i++) printf("%d ",B[i][j]); printf("\n"); }*/ if (A[P][3]==0) { printf("Charlie cannot buy coffee.\n"); } else { i=P; for(j=3;j>=0;j--) { R[j]=B[i][j]; i=i-(R[j]*H[j]); } printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",R[0],R[1],R[2],R[3]); } } return 0; }