Pagini recente » Istoria paginii utilizator/stoia_andrei_alexandru_324cb | Cod sursa (job #343043) | Diferente pentru preoni-2007/runda-3/solutii intre reviziile 53 si 20 | Cod sursa (job #2860856) | Cod sursa (job #2765098)
#include <fstream>
#include <iostream>
using namespace std;
int n, S;
void read() {
ifstream f("1-sir.in");
f >> n >> S;
f.close();
}
int rez = 0;
int dp[2][256 * 257 + 1]; // suma maxima poate fi n * (n + 1) / 2 la care se inmulteste cu 2 pentru numere nagative -> n * (n + 1)
// prima dimensiune este 2 pentru a face rucsacul cu 2 linii, nu cu n linii (dp[i] depinde doar de dp[i - 1])
const int MOD = 194767;
void solve() {
// rezultatul pentru S si -S este acelasi
if (S < 0)
S = -S;
// observam ca daca S este mai mult de n * (n + 1) / 2, rezultatul este 0
if (S > n * (n + 1) / 2)
return;
// dp rucsac pentru rezolvare cu tratarea numerelor negative cu constanta C
int C = n * (n + 1) / 2;
int i, j, k;
dp[1][0 + C] = 1;
for (i = 2; i <= n; i++) {
for (j = 0; j <= S + C; j++)
dp[i % 2][j] = 0;
for (j = 0; j <= S + C; j++) {
if (j - (i - 1) >= 0)
dp[i % 2][j] = (dp[i % 2][j] + dp[1 - i % 2][j - (i - 1)]) % MOD;
if (j + (i - 1) >= 0)
dp[i % 2][j] = (dp[i % 2][j] + dp[1 - i % 2][j + (i - 1)]) % MOD;
}
}
rez = dp[n % 2][S + C];
}
void output() {
ofstream g("1-sir.out");
g << rez;
g.close();
}
int main() {
read();
solve();
output();
return 0;
}