Cod sursa(job #2765097)

Utilizator DragosC1Dragos DragosC1 Data 24 iulie 2021 23:43:22
Problema 1-sir Scor 50
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.43 kb
#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 <= n * (n + 1); j++)
            dp[i % 2][j] = 0;
        for (j = 0; j <= n * (n + 1); 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;
}