Friday, 2 September 2016

UVa 357 - Let Me Count The Ways

#include<bits/stdc++.h>
#define mod 100000007
using namespace std;
typedef long long ll;
ll arr[300009],coin[6]={0,1,5,10,25,50};
int main()
{
    ll i,j,k,l,m,n,test,make;
    while(cin>>make)
    {
        n=5;
        memset(arr,0,sizeof(arr));
        arr[0]=1;
        ll sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=coin[i];j<=make;j++)
            {
                arr[j]=(arr[j])+(arr[j-coin[i]]);
            }
        }
        cout<<"There ";
        if(arr[make]<=1)
            cout<<"is only ";
        else
            cout<<"are ";
        cout<<arr[make]<<" ";
        if(arr[make]<=1)
            cout<<"way";
        else
            cout<<"ways";
        cout<<" to produce "<<make<<" cents change."<<endl;
    }
    return 0;
}


No comments:

Post a Comment