Pagini recente » Cod sursa (job #1129324) | Cod sursa (job #659591) | Cod sursa (job #3236520) | Cod sursa (job #1228234) | Cod sursa (job #2855741)
// Obs: O suma cu i elemente o construiesc in functie de primul semn
// primul semn il adaug la solutiile anterioare, iar acesta imi afecteaza solutia cu i-1 (+ sau -, in functie de semnul ales)
// de aici iese recurenta
#include <bits/stdc++.h>
using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
const int NMAX = 300, MOD = 194767;
int dp[2][NMAX * NMAX]; // dp[i][j] - cate sume de i elemente am, suma si suma j
inline void swapLines()
{
int i;
for(i = 0; i < NMAX * NMAX; ++i)
dp[0][i] = dp[1][i];
}
int main()
{
int n, s;
fin >> n >> s;
s = abs(s);
if(s > n * (n + 1) / 2)
{
fout << "0";
return 0;
}
int lcurent, sumMax = n * (n + 1) / 2, sumCurrent;
dp[1][0] = 1;
for(lcurent = 2; lcurent <= n; ++lcurent)
{
swapLines();
for(sumCurrent = 0; sumCurrent <= sumMax; ++sumCurrent)
{
dp[1][sumCurrent] = dp[0][sumCurrent + lcurent - 1] + dp[0][abs(sumCurrent - lcurent + 1)];
if(dp[1][sumCurrent] >= MOD)
dp[1][sumCurrent] -= MOD;
}
}
fout << dp[1][s];
return 0;
}