Cod sursa(job #7326)

Utilizator victorsbVictor Rusu victorsb Data 21 ianuarie 2007 13:27:09
Problema 1-sir Scor 20
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.54 kb
#include <cstdio>
#include <string.h>
#define Nmax 32*4 
#define Smax 32*32*2
#define sum(x) (x)+1000
#define nr(x) (x)+60

const int modul = 194767;

int n, i, j, s, k, s1, s2, sol;
int d1[Nmax][Smax], d2[Nmax][Smax];

void citire()
{
    scanf("%d %d\n", &n, &s);
}

void solve()
{
    //memset(d,0,sizeof(d));
    d2[nr(0)][sum(0)] = 1;
    s1 = - (s2 = n*(n-1)/2);
    for (i=2; i<=n; ++i)
    {
        memset(d1,0,sizeof(d1));
        for (j=-n+1; j<=n-1; ++j)
            for (k=s1; k<=s2; ++k)
            {
                d1[nr(j)][sum(k)] += d2[nr(j-1)][sum(k-j)] + d2[nr(j+1)][sum(k-j)];
                if (d1[nr(j)][sum(k)] >= modul)
                   d1[nr(j)][sum(k)] -= modul;
                //printf("%d %d %d - %d\n", i, j, k, d[i][nr(j)][sum(k)]);
            }
        memcpy(d2,d1,sizeof(d1));
    }
    for (i=-n+1; i<=n-1; ++i)
    {
        sol += d2[nr(i)][sum(s)];
        if (sol >= modul)
           sol -= modul;
    }
    printf("%d",sol);
}

int main()
{
    freopen("1-sir.in","r",stdin);
    freopen("1-sir.out","w",stdout);
    citire();
    if ((n + 1)%4 == 0 && s % 2 == 0)
    {
        printf("0\n");
        return 0;
    }
    else if (((n+1)%2 == 0) && ((n+1)%4 != 0) && s % 2 == 1)
    {
        printf("0\n");
        return 0;
    }
    else if ((n%4 == 0) && s % 2 == 1)
    {
        printf("0\n");
        return 0;
    }
    else if ((n%2 == 0) && (n%4!=0) && s % 2 == 0)
    {
        printf("0\n");
        return 0;
    }
    solve();
    return 0;
}