Sunday, August 17, 2014

uva : 357 - Let Me Count The Ways


#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int coin[5]={50,25,10,5,1};
int main()
{
    //freopen("output.txt","w",stdout);
    int i,j,k,l,m,c;
    int n;
    while(scanf("%d",&n)==1)
    {
        m=n;
       long long nway[100001];
       for(i=0;i<100001;i++)nway[i]=0;
       nway[0]=1;
       for(i=0;i<5;i++)
       {
           c=coin[i];
           for(j=c;j<=n;j++)
           {
               nway[j]+=nway[j-c];
           }
       }
       if(nway[n]==1){printf("There is only %lld way to produce ",nway[n]);printf("%d cents change.\n",m);}
       else {printf("There are %lld ways to produce ",nway[n]);printf("%d cents change.\n",m);}
    }
    return 0;
}

No comments:

Post a Comment