Cod sursa(job #14296)

Utilizator azotlichidAdrian Vladu azotlichid Data 8 februarie 2007 17:58:19
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.65 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>

#define NMAX    260
#define SMAX    65540
#define MODULO  194767
#define ABS(x)  ((x) >= 0 ? (x) : -(x))

int N, S, a[NMAX][SMAX];

int dfs(int N, int S)
{
    if ((S = ABS(S)) > N * (N - 1) / 2) return 0;
    if (N == 1) return a[N][S] = (S == 0 ? 1 : 0);
    if (a[N][S] != -1) return a[N][S];

    return a[N][S] = (dfs(N - 1, S - N + 1) + dfs(N - 1, S + N - 1)) % MODULO;
}

int main(void)
{
    freopen("1sir.in", "r", stdin);
    freopen("1sir.out", "w", stdout);
    scanf("%d %d", &N, &S);
    memset(a, 0xFF, sizeof(a));
    printf("%d\n", dfs(N, S));
    return 0;
}