http://www.snowoat.tk/?p=161
328K  360MS
#include"iostream"
using namespace std;
#define max(a,b) (a>b?a:b)
int main()
{
    int dp[10010],num[10010][2];
    int a,data[4],i,j,value[4]={1,5,10,25};
    while(scanf("%d%d%d%d%d",&a,&data[0],&data[1],&data[2],&data[3])&&a!=0)
    {
        for(int i=0;i<=a;i++)dp[i]=-100000;
        dp[0]=0;
        for(i=0;i<4;i++)
        {
            if(value[i]*data[i]>=a){
                for(j=value[i];j<=a;j++)
                    if(dp[j-value[i]]+1>dp[j]){dp[j]=dp[j-value[i]]+1;num[j][0]=i;num[j][1]=1;}
            
            }else{
                int k=1;
                while(k<data[i]){
                    for(j=a;j>=k*value[i];j--)
                        if(dp[j-k*value[i]]+k>dp[j]){dp[j]=dp[j-k*value[i]]+k;num[j][0]=i;num[j][1]=k;}
                    data[i]-=k;
                    k*=2;
                }
                for(j=a;j>=data[i]*value[i];j--)
                    if(dp[j-data[i]*value[i]]+data[i]>dp[j]){dp[j]=dp[j-data[i]*value[i]]+data[i];num[j][0]=i;num[j][1]=data[i];}
            }
        }
        if(dp[a]<=0)cout<<"Charlie cannot buy coffee."<<endl;
        else{
            data[0]=data[1]=data[2]=data[3]=0;
            while(a){
                i=num[a][0];
                data[i]+=num[a][1];
                a-=value[i]*num[a][1];
            }
            printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n",data[0],data[1],data[2],data[3]);
        }
    }
}