ACM (UVa) : 11137


#include
#include
using namespace std;

long nway[10001];

void Count() {
int i, j, c;
int Coin[] = {1, 8, 27, 64, 125, 216, 343, 512, 729, 1000, 1331, 1728, 2197, 2744, 3375, 4096, 4913, 5832, 6859, 8000, 9261};
reverse (Coin, Coin + 21);
nway[0] = 1;
for(i = 0; i < 21; i++) { c = Coin[i]; for(j = c; j<=10000; j++) { nway[j] += nway[j-c]; } } } int main() { long n; Count(); while(scanf("%ld",&n) != EOF) { // n must be smaller than 1001 printf("%ld\n",nway[n] ); } return 0; } [/sourcecode]

6 thoughts on “ACM (UVa) : 11137

  1. @发给
    suppose, nway [5] = 7
    that means, you can make coin 5, in 7 different ways
    for example, u have only coins 1, 2, 3
    so, in how may ways u can make 5 ?
    nway [5] = nway [5-1] + nway [5-2] + nway [5-3]
    because,
    nway [5-1] + coin 1 = 5
    nway [5-2] + coin 2 = 5
    nway [5-3] + coin 3 = 5

  2. @nayem,
    the complexity of the problem is n * m
    n = number of coins
    m = limits of the coins
    so its possible to solve the problem using above method, even when the limit is about 10000

  3. i don’t able to calculate
    440022018293 for 9999
    because i don’t know how to work for big input !!!!
    unsigned long is not applicable there.
    then what i need to do??
    please give me some hints…

  4. @nayem
    Data type: long long (gcc) or __int64 (vc)
    Range: –9,223,372,036,854,775,808 to 9,223,372,036,854,775,807

    Data type: unsigned long long (gcc) or unsigned __int64 (vc)
    Range: 0 to 18,446,744,073,709,551,615

    any of these is more than enough to store values
    anytime u can use double. though it’s useful to know how to deal with big integer. for now, u can use long long data type in gcc compiler.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s