Cod sursa(job #8006)

Utilizator ProstuStefan-Alexandru Filip Prostu Data 23 ianuarie 2007 16:37:32
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>
#include <algorithm>

using namespace std;

const int NMAX = 256;
const int SMAX = 32768;
const int MOD = 194767;

int N, S;
int DP[2][SMAX];

void read() {
	FILE *fin = fopen("1-sir.in", "rt");

	fscanf(fin, " %d %d", &N, &S);

	fclose(fin);
}

void dinamica() {
	int i, j, k, k1, stop, t;

	DP[1][0] = 1;

	for (i = 2; i <= N; ++i) {
		stop = (i * (i - 1)) >> 1;
		k = i & 1; k1 = k ^ 1;

		for (j = 0; j <= stop; ++j) {
			t = j - i + 1;

			DP[k][j] += t < 0 ? DP[k1][-t] : DP[k1][t] + DP[k1][j + i - 1];

			if (DP[k][j] >= MOD) DP[k][j] -= MOD;
		}
	}
}

void write() {
	FILE *fout = fopen("1-sir.out", "wt");

	fprintf(fout, "%d\n", DP[N & 1][S]);

	fclose(fout);
}

int main() {

	read();

	dinamica();

	write();

	return 0;
}