Pagini recente » Cod sursa (job #1053418) | Cod sursa (job #1505459) | Cod sursa (job #2302643) | Cod sursa (job #2578071) | Cod sursa (job #2070913)
#include <fstream>
#include <cmath>
#define DIM 260
#define MOD 194767
using namespace std;
ifstream f("1-sir.in");
ofstream g("1-sir.out");
int n, dp[2][DIM * DIM / 2], m, s, t;
int main()
{
f>>n>>s;
m = n * (n + 1) / 2;
dp[0][0] = 1; // dp[i][j] = numarul de moduri de a forma un subsir de lungime i cu suma j
//daca pun 1 pe pozitia i in sirul cu sume partiale suma totala va creste cu n - i + 1
//iar daca pun -1 va scadea cu n - i + 1 deci din aceste 2 cazuri pot face un sir cu suma j
t = 1;
for(int i = 2; i <= n; ++ i, t = 1 - t)
for(int j = 0; j <= m; ++ j){
int val = j - n + i - 1;
val = abs(val);
dp[t][j] = (dp[1 - t][val] + dp[1 - t][j + (n - i + 1)]) % MOD;
}
g<<dp[1 - t][s];
return 0;
}