deleted:

Edited by author 24.12.2014 23:56

input 5
output 20

input 6
output 28

input 7
output 44

input 100
output 4503599627370492

input 1000
output 13093562431584567480052758787310396608866568184172259157933165472384535185618698219533080369303616628603546736510240284036869026183541572213314110357500

input 2000
output 42860344287450692837937001962400072422456192468221344297750015534814042044997444899727935152627834325103786916702125873007485811427692561743938310298794299215738271099296923941684298420249484567511816728612185899934327765069595070236662175784308251658284785910746168670641719326610497547348822672277500

#include<stdio.h>

int a[2001][330];

int main()
{
    int n;

    for(int i=0; i<2001; i++)
    {
        for(int j=0; j<330; j++)
        {
            a[i][j]=0;
        }
    }

    scanf("%d", &n);

    a[1][329]=1;
    a[2][329]=4;
    a[3][329]=8;

    for(int i=4; i<2001; i++)
    {
        for(int j=329; j>0; j--)
        {
            if((i%2)==0)
            {
                a[i][j]=a[i][j]+(2*a[i-1][j])%10-a[i-2][j];
                if(a[i][j]<0)
                {
                    a[i][j]=a[i][j]+10;
                    a[i][j-1]=a[i][j-1]-1;
                }
                if(a[i][j]>10)
                {
                    a[i][j]=a[i][j]%10;
                    a[i][j-1]=a[i][j-1]+a[i][j]/10;
                }
                if(2*a[i-1][j]>9)
                {
                    a[i][j-1]=a[i][j-1]+(2*a[i-1][j])/10;
                }
            }
            else
            {
                a[i][j]=a[i][j]+(3*a[i-1][j])%10-(2*a[i-2][j])%10;
                if(a[i][j]<0)
                {
                    a[i][j]=a[i][j]+10;
                    a[i][j-1]=a[i][j-1]-1;
                }
                if(a[i][j]>10)
                {
                    a[i][j]=a[i][j]%10;
                    a[i][j-1]=aa[i][j-1]+[i][j]/10;
                }
                if(3*a[i-1][j]>9)
                {
                    a[i][j-1]=a[i][j-1]+(3*a[i-1][j])/10;
                }
                if(2*a[i-2][j]>9)
                {
                    a[i][j-1]=a[i][j-1]-(2*a[i-2][j])/10;
                }
            }
        }
    }

    for(int i=0; i<330; i++)
    {
        if(a[n][i]!=0)
        {
            for(int j=i; j<330; j++)
            {
                printf("%d", a[n][j]);
            }
            printf("\n");
            goto A;
        }
    }
A:
    return 0;
}

All tests are right, but I can't understand why WA12?

I used DP for solving this problem, and have AC in 0.015 sec. as many other Timus members. But, there are some members who take AC in 0.001 sec. So, my question is: is there some formula for this problem or this people take so incredible result with very hard optimization?

124
188 ?