No, your 'dimamic program' shouldn't 'word' because you have to use big numbers...


Edited by author 23.03.2005 06:42

Thank you for help. I understand my mistake.

You know long arithmetic? This problem solved usin it.

Use long arithmetic and algorithm 1009 :)))

Just look at my page:
acmsolver.timus.ru
There is a description how to solve it.
SAV

u can use a cycle instead of recursion.
and the change array (int)ways[200] into (int)ways[3][2000]; because the result will has maore than 100 digits, mathematic arithmetic is needed. i change you programme as follow:

//dynamic programming

#include <iostream.h>
#include <stdio.h>
int ways[3][20000]={0};
int ADD(int a[], int b[], int c[]);
int MUL(int a[], int k);
int main()
{
    long n, k, i, j;
    cin>>n>>k;
    ways[0][1] = 1;
    ways[0][0] = 1;
    ways[1][1] = k-1;
    ways[1][0] = 1;
    for (i=2; i<=n; i++)
    {
         ADD(ways[2], ways[1], ways[0]);
        MUL(ways[2], k-1);
        j = 2;
        i++;
        if (i>n)
            break;
        ADD(ways[0], ways[2], ways[1]);
        MUL(ways[0], k-1);
        j = 0;
        i++;
        if (i>n)
            break;
        ADD(ways[1], ways[0], ways[2]);
        MUL(ways[1], k-1);
        j = 1;
    }
    for (i=ways[j][0]; i>=1; i--)
    {
        cout<<ways[j][i];
    }
    return 0;
}

int ADD(int a[], int b[], int c[])
{
    int i, remainder, carry;
    for (i=1, carry=0; i<=b[0] && i<=c[0]; i++)
    {
        remainder = (b[i] + c[i] + carry) % 10;
        carry = (b[i] + c[i] + carry) / 10;
        a[i] = remainder;
    }
    for (; i<=b[0]; i++)
    {
        remainder = (b[i] + carry) % 10;
        carry = (b[i] + carry) / 10;
        a[i] = remainder;
    }
    for (; i<=c[0]; i++)
    {
        remainder = (c[i] + carry) % 10;
        carry = (c[i] + carry) / 10;
        a[i] = remainder;
    }
    if (carry==1)
    {
        a[i++] = carry;
    }
    a[0] = i - 1;
    return 0;
}

int MUL(int a[], int k)
{
    int i, remainder, carry=0;
    for (i=1; i<=a[0]; i++)
    {
        remainder = (a[i] * k + carry) % 10;
        carry = (a[i] * k + carry) / 10;
        a[i] = remainder;
    }
    for (; carry>0; i++)
    {
        remainder = carry % 10;
        carry = carry / 10;
        a[i] = remainder;
    }
    a[0] = i - 1;
    return 0;
}

Quote:
"You may assume that 2 <= K <= 10; 2 <= N; 4 <= N+K <= 180."

This means you have to use BIG numbers!

 Your logic seems OK (I didn't check it, but it seems). Your problem
is that the numbers might (and will) be bigger than a longint (not in
the input but in the output).

you can use an array of integers for that huge number . when
n = 1800 and k = 10 the answer have about 3600 digits !!! and
you cant store it in nor long nor any other variable.
in this problem you must find a recursive relations . ( not to
consider all answer ). it has a nice soloution . if you use
this method but not receive the correct answer mail me at :
ioi_khafan@hotmail.com . thanks . bye

b[i]*int may be more than MaxLongInt