Cod sursa(job #613873)

Utilizator Magnuscont cu nume gresit sau fals Magnus Data 4 octombrie 2011 22:29:41
Problema Substr Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.34 kb
#include <cstdio>

inline int max(int x,int y){if (x>y) return x;else return y;}

int d[101][101][101];

int main()
{
    int n,m,i,j,k,x,y,t,aux;
    freopen("sg1.in","r",stdin);
    freopen("sg1.out","w",stdout);
    scanf("%d %d %d %d",&n,&m,&x,&y);
    for (i=1;i<=n;++i)
    {
        d[i][1][0]=1;
        d[i][1][1]=1;
        for (j=1,t=0;j<=d[i][1][0]||j<=d[i-1][1][0]||t;++j,t/=10)
            d[i][1][j]=(t+=d[i][1][j]+d[i-1][1][j])%10;
        d[i][1][0]=j-1;
        for (j=2;j<=m;++j)
        {
            aux=max(0,i-x-1);
            for (k=0;k<=d[i-1][j][0];++k)
                d[i][j][k]=d[i-1][j][k];
            for (k=1,t=0;k<=d[i][j][0]||k<=d[aux][j-1][0]||t;++k,t/=10)
                d[i][j][k]=(t+=d[i][j][k]+d[aux][j-1][k])%10;
            d[i][j][0]=k-1;
            aux=max(0,i-y-2);
            for (k=1;k<=d[i][j][0];++k)
                d[i][j][k]-=d[aux][j-1][k];
            for (k=1;k<=d[i][j][0];++k)
                if (d[i][j][k]<0)
                {
                    d[i][j][k]+=10;
                    --d[i][j][k+1];
                }
            while (!d[i][j][d[i][j][0]]&&d[i][j][0]>1)
                --d[i][j][0];
        }
    }
    if (d[n][m][0]==0)
        d[n][m][0]=1;
    for (i=d[n][m][0];i;--i)
        printf("%d",d[n][m][i]);
    printf("\n");
    return 0;
}