Pagini recente » Cod sursa (job #815955) | Cod sursa (job #19828) | Cod sursa (job #4805) | Cod sursa (job #2733340) | Cod sursa (job #2453650)
#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;
}