Cod sursa(job #2453650)

Utilizator mvcl3Marian Iacob mvcl3 Data 4 septembrie 2019 22:41:51
Problema 1-sir Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.17 kb
#include<fstream>
using namespace std;

inline bool canContinueAdding(int& idx, int& n, int& totalSum, int& sum, int ref) {
	int s = 0;
	if (ref < 0) {
		s = -(ref * (ref - 1)) / 2;
		s = s + ((n - idx + ref) * (n - idx + ref + 1)) / 2;
		if (totalSum + s < sum)
			return false;

		return true;
	}
	else {
		s = (ref * (ref + 1)) / 2;
		s = s - ((n - idx - ref) * (n - idx - ref + 1)) / 2;
		if (totalSum + s > sum)
			return false;

		return true;
	}
}

void compute(int s[], int idx, int& n, int& sum, int& cnt, int totalSum) {
	totalSum += s[idx - 1];

	if (idx == n + 1) {
		if (sum == totalSum)
			cnt++;

		return;
	}


	if (canContinueAdding(idx, n, totalSum, sum, s[idx - 1] - 1)) {
		s[idx] = s[idx - 1] - 1;
		compute(s, idx + 1, n, sum, cnt, totalSum);
	}


	if (canContinueAdding(idx, n, totalSum, sum, s[idx - 1] + 1)) {
		s[idx] = s[idx - 1] + 1;
		compute(s, idx + 1, n, sum, cnt, totalSum);

	}
}




int main() 
{
	ifstream in("1-sir.in");
	ofstream out("1-sir.out");

	int n, sum, cnt = 0, s[257];

	in >> n >> sum;

	if (sum < 0)
		sum = -sum;

	s[1] = 0;
	compute(s, 2, n, sum, cnt, 0);

	out << cnt;

	return 0;
}