Cod sursa(job #7700)

Utilizator filipbFilip Cristian Buruiana filipb Data 21 ianuarie 2007 23:01:50
Problema 1-sir Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <stdio.h>
#define min(a, b) ((a < b) ? a : b)
#define MOD 194767
#define NMax 258

int N, S, M[2][NMax * (NMax + 1) / 2];

int main(void)
{    
    int i, j, s1, crt = 0, prev = 0;
    
    freopen("1-sir.in", "r", stdin);
    freopen("1-sir.out", "w", stdout);

    scanf("%d %d", &N, &S);
    if (S > N * (N-1) / 2 || S < - N * (N-1) / 2)
       printf("0\n");
    else
    {
        if (S < 0) S = -S;

        M[0][0] = 1;
        for (i = 2; i <= N; i++)
        {            
            prev = (i & 1); crt = !prev; 
            for (j = 0; j <= i * (i-1) / 2; j++)
            {
                if (j-i+1 < 0) s1 = M[prev][i-1-j]; else s1 = M[prev][j-i+1];
                s1 += M[prev][j+i-1];
                if (s1 >= MOD) s1 -= MOD;
                M[crt][j] = s1;
            }            
            
        }
        
        printf("%d\n", M[crt][S]);
    }
    
    return 0;    
}