Cod sursa(job #1609813)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 23 februarie 2016 00:58:37
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("1-sir.in");
ofstream fout("1-sir.out");

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

int n; int s;

int d[SMAX];
int oldD[SMAX];



int sol[30]; int cnt; int sum;

int mod(int x) { return x > 0 ? x : -x; }

void back(int k) {

	if(k == n + 1) {
		if(s == sum) 
			cnt++;
		
	} else 
		for(int i = -n; i <= n; ++i)
			if(mod(sol[k - 1] - i) == 1) {
				sum += i;
				sol[k] = i;
				back(k + 1);
				sum -= i;
			}
}

int main() {

	fin >> n >> s;

	s = (n - 1) * n / 2  - s;

	s /= 2;

	d[0] = 1; //0 1 2 3 4 ...

	/* La un pas putem alege sa facem alegerea inversa (-1) si astfel toate
	valorile urmtoare se modifica cu 2 unitati, astfel putem modifica cu 2, 4, 6 suma maxima, scazand din ea aceste nr
	*/

	int upperBound = 0; int limit;

	for(int i = 1; i <= n - 1; i++) {

		upperBound += i;
		limit = min(s, upperBound);

		for(int j = 0; j <= limit; ++j) 
			oldD[j] = d[j];

		for(int j = 0; j <= limit; ++j) {
			
			if(oldD[j] == 0) continue;

			d[j + i] += oldD[j];
			
			if(d[j + i] >= MOD)
				d[j + i] -= MOD; 
		}
	}

	fout << d[s] << '\n'; 

	return 0;
}