Cod sursa(job #7194)

Utilizator varuvasiTofan Vasile varuvasi Data 21 ianuarie 2007 13:02:51
Problema 1-sir Scor 10
Compilator cpp Status done
Runda preONI 2007, Runda 1, Clasele 11-12 Marime 1.18 kb
#include <stdio.h>
#include <string.h>
#define MaxS 110000

#define MaxN 521

int N, S;
const int SHIFT = 55000;
const int shift = 260;
int A[2][MaxS][MaxN];
int mat[MaxS][MaxN];
int lc = 1, lp = 0;
int main()
{
    int i, j, k;

    FILE *fin = fopen("1-sir.in", "rt");
    fscanf(fin, "%d %d", &N, &S);
    fclose(fin);

    A[0][SHIFT][shift] = 1;

    for (i = 2; i <= N; i++, lc = !lc, lp = !lp)
    {
        //memset(A[lc], 0, sizeof(A[lc]));
        for (j = SHIFT-(i*(i+1))/2; j <= SHIFT+(i*(i+1))/2; j++)
	    for (k = -N+1; k < N; k++)
	    {
    	    int x = k + 1;
    	    if (mat[j+x][shift+x] != i) A[lc][j+x][shift+x] = 0, mat[j+x][shift+x] = i;
    	    A[lc][j+x][shift+x] += A[lp][j][shift+k];
    	    A[lc][j+x][shift+x] %= 194767;
    	    x = k - 1;
    	    if (mat[j+x][shift+x] != i) A[lc][j+x][shift+x] = 0, mat[j+x][shift+x] = i;
    	    A[lc][j+x][shift+x] += A[lp][j][shift+k];
    	    A[lc][j+x][shift+x] %= 194767;
	    }
	}

    int Val_fin = 0;
    for (i = -N; i <= N; i++)
	Val_fin += A[lp][SHIFT+S][shift+i];

    FILE *fout = fopen("1-sir.out", "wt");
    fprintf(fout, "%d", Val_fin);
    fclose(fout);

    return 0;
}