Pagini recente » Statisticile problemei Blaturi | Nozero | Profil ciureasilvia | Rating Melvin Abibula (MerlinTheWizard) | Cod sursa (job #3364059)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("1-sir.in");
ofstream fout("1-sir.out");
const int MOD = 194767;
const int OFFSET = 32640;
int n, k;
int dp[2 * OFFSET + 3][2]; //dp[sum][stare]
int last = 0, curent = 1;
int main()
{
fin >> n >> k;
int sumMax = n * (n - 1) / 2;
if(k < -sumMax || k > sumMax) fout << 0;
else {
dp[0 + OFFSET][last] = 1;
for(int i=1; i<=n-1; i++) {
int maxim = i * (i - 1) / 2;
int minim = -maxim;
for(int j=minim; j<=maxim; j++) dp[j + OFFSET][curent] = 0; //reset
int val = i; //am ca termeni +-i
for(int j=minim; j<=maxim; j++) {
dp[j + val + OFFSET][curent] += dp[j + OFFSET][last];
if(dp[j + val + OFFSET][curent] >= MOD) dp[j + val + OFFSET][curent] -= MOD;
}
val = -i;
for(int j=minim; j<=maxim; j++) {
dp[j + val + OFFSET][curent] += dp[j + OFFSET][last];
if(dp[j + val + OFFSET][curent] >= MOD) dp[j + val + OFFSET][curent] -= MOD;
}
swap(last, curent);
}
fout << dp[k + OFFSET][last];
}
return 0;
}
/**
not x1, x2, .., xn-1 pasii pe care ii fac +-1
elem vor fi v1 = 0 ; v2 = x1 ; v3 = x1 + x2 ; ... ; vn = x1 + .. + xn-1
=> k = v1 + ... + vn = (n-1)x1 + (n-2)x2 + ... + xn-1 = +-(n-1) +-(n-2) +- ... +-1
fac 2 rucsac uri
**/