OJ Board

Code: Select all

[u][b]THIS  REMOVED BCOZ I GOT AC.......[/b][/u]

Code: Select all

#include<stdio.h>
#include<iostream>
#define MAX 30500
long long  array[30500]={0};
long long  coin[]={1,5,10,25,50};
int main(void)
{
        long long  cents=0;
        array[0]=1;
        array[1]=1;
        for(long long  i=0;i<5;i++)
        {
                for(long long  j=1;j<MAX;j++)
                {
                        if(coin[i]+j<MAX)
                        array[coin[i]+j]+=array[j];
                }
        }
        while(scanf("%lld",&cents)!=EOF)
        {
                if(array[cents]==1) printf("There is only 1 way to produce %lld cents change.\n",cents);
                else    printf("There are %lld ways to produce %lld cents change.\n",array[cents],cents);
        }
}

Code: Select all

5

Code: Select all

0
There is only 1 way to produce 0 cents change.
1
There is only 1 way to produce 1 cents change.
4
There is only 1 way to produce 4 cents change.
5
There are 2 ways to produce 5 cents change.
10
There are 4 ways to produce 10 cents change.
11
There are 4 ways to produce 11 cents change.
17
There are 6 ways to produce 17 cents change.
99
There are 252 ways to produce 99 cents change.
300
There are 9590 ways to produce 300 cents change.
1000
There are 801451 ways to produce 1000 cents change.
2000
There are 11712101 ways to produce 2000 cents change.
3000
There are 57491951 ways to produce 3000 cents change.
4000
There are 178901001 ways to produce 4000 cents change.
5000
There are 432699251 ways to produce 5000 cents change.
6000
There are 891646701 ways to produce 6000 cents change.
7000
There are 1644503351 ways to produce 7000 cents change.
8000
There are -1498938095 ways to produce 8000 cents change.
9000
There are 172016955 ways to produce 9000 cents change.
10000
There are -1795806091 ways to produce 10000 cents change.
30000
There are -2033701091 ways to produce 30000 cents change.