Cod sursa(job #2694808)

Utilizator iancupoppPopp Iancu Alexandru iancupopp Data 10 ianuarie 2021 19:14:27
Problema 1-sir Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <fstream>
#include <queue>
#include <map>

using namespace std;

const int N = 256;
const int BASE = 256 * 257 / 2;
const int MOD = 194767;

struct elem {
    int l;
    int s;
    int ult;
    int nr;
};

struct p {
    int l;
    int s;
    int ult;
    bool operator<(const p& P) const {
        if (l != P.l) return l < P.l;
        if (s != P.s) return s < P.s;
        return ult < P.ult;
    }
};

int main() {
    ifstream in("1-sir.in");
    ofstream out("1-sir.out");

    int n, s;
    in >> n >> s;

    map<p, int> m;
    queue<elem> q;
    q.push({ 1, BASE, 0, 1 });
    while (!q.empty()) {
        elem& crt = q.front();
        m[{ crt.l, crt.s, crt.ult}] += crt.nr;
        m[{ crt.l, crt.s, crt.ult}] %= MOD;

        if (crt.l < n) {
            q.push({ crt.l + 1, crt.s + crt.ult + 1, crt.ult + 1, m[{ crt.l, crt.s, crt.ult }] });
            q.push({ crt.l + 1, crt.s + crt.ult - 1, crt.ult - 1, m[{ crt.l, crt.s, crt.ult }] });
        }

        q.pop();
    }
    
    int rez = 0;
    for (int i = 0; i <= BASE * 2; ++i)
        rez = (rez + m[{ n, s + BASE, i }]) % MOD;

    out << rez;

    in.close();
    out.close();
    return 0;
}