Cod sursa(job #7548)

Utilizator mockeBarca Cristian Mihai mocke Data 21 ianuarie 2007 17:09:09
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ABS(a) ( (a) < 0 ? -(a) : (a) )
#define NMAX 32560
#define MOD 194767

int N, S, A[2*NMAX + 1], Ap[2*NMAX + 1];
int MaxV;
int i, sp, temp;

#define A (A + NMAX)
#define Ap (Ap + NMAX)

int main()
{
	freopen("1-sir.in" , "r", stdin);
	freopen("1-sir.out", "w", stdout);
	
	scanf("%d %d", &N, &S);
	
	MaxV = N*(N-1)/2;
	
	if (ABS(S) > MaxV) { printf("0\n"); return 0; }
	
	Ap[0] = 1;
	
	for (i = 1; i < N; i++) 
	{ 
		for (sp = -MaxV; sp <= MaxV; sp++) 
		{ 
			temp = i * (i+1)/2; 
			
			if (sp > temp || sp < -temp) { Ap[sp]=0; continue; }
			
			A[sp] = (Ap[sp - i] + Ap[sp + i]) % MOD; 
		} 
		
		for (sp = -MaxV; sp <= MaxV; sp++) Ap[sp] = A[sp]; 
	}
	
	
	printf("%d\n", Ap[S]);
	
	return 0;
}