Poj Solution 1787

http://poj.org/problem?id=1787

#include<iostream>
#include"memory.h"
using namespace std;

char set[10000];
int use[10000][4];
long total[10000];
int money[4]={1,5,10,25};

int limit[4],p;


void doit()
{int i,j,h,k;
memset(set,0,10000*sizeof(char));
memset(use,0,10000*4*sizeof(int));
set[0]=1;
total[0]=0;
for(i=0;i<4;i++)
for(j=0;j<=p-money[i];j++)
{h=j+money[i];
if(set[j]&&(!set[h]||total[h]<total[j]+1)&&use[j][i]<limit[i])
    {set[h]=1;
    for(k=0;k<4;k++)use[h][k]=use[j][k];
    use[h][i]=use[j][i]+1;
    total[h]=total[j]+1;
    }
}

return;
}

int main()
{int i;
    while(1)
{cin>>p;
for(i=0;i<4;i++)cin>>limit[i];
if(p==0)break;
doit();
if(set[p])cout<<"Throw in "<<use[p][0]<<" cents, "<<use[p][1]<<" nickels, "<<use[p][2]<<" dimes, and "<<use[p][3]<<" quarters."<<endl;
else cout<<"Charlie cannot buy coffee."<<endl;
}
return 0;
}