Cod sursa(job #3364059)

Utilizator Cyb3rBoltSbora Ioan-David Cyb3rBolt Data 28 august 2026 18:53:00
Problema 1-sir Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.44 kb
#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
**/