Cod sursa(job #7463)

Utilizator astronomyAirinei Adrian astronomy Data 21 ianuarie 2007 15:58:20
Problema 1-sir Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.01 kb
#include <stdio.h>

#define MOD 194767
#define MAXN 256
#define MAXS (255*256+256)

const int VAL = 255*128;

int N, S, V;
int A[2][MAXS];

int solve(void)
{
    int n, p, s, t, u = 0, v = 1, res = 0;

    A[u][0+VAL] = 1;

    for(n = N; n >= 2; n--)
    {
        for(s = (-1)*V; s <= V; s++)
        {
            A[v][s+VAL] = 0;
            if( (t = s-(N-n)-1+VAL) < MAXS )
                A[v][s+VAL] += A[u][t];
            if( (t = s+(N-n)+1+VAL) < MAXS )
                A[v][s+VAL] += A[u][t];
            if(A[v][s+VAL] >= MOD)
                A[v][s+VAL] -= MOD;
        }
        u ^= 1, v ^= 1;
    }
    
    res = A[u][S+VAL];

    return res;

}

int main(void)
{
    freopen("1-sir.in", "rt", stdin);
    freopen("1-sir.out", "wt", stdout);

    int i, j;

    scanf("%d %d\n", &N, &S);

    V = (N-1)*N/2;

    if(S < (-1)*V || S > V)
    {
        printf("0\n");
        return 0;
    }

    printf("%d\n", solve());

    return 0;
}