Cod sursa(job #1418376)

Utilizator dinuandAndrei-Mario Dinu dinuand Data 12 aprilie 2015 21:25:15
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

#define MAXN 257
#define MAXS 33000
#define MOD 194767

std::ifstream in("1-sir.in");
std::ofstream out("1-sir.out");

inline int module(int nb)
{
    return (nb > 0) ? nb : (nb * (-1));
}

int main()
{
    int N, S;
    in >> N >> S;

    if (N * (N - 1) / 2 < S) {
        out << 0 << '\n';
        return 0;
    }

    std::vector<std::vector<int> >strings(2, std::vector<int>(MAXS, 0));

    S = module(S);

    strings[1][0] = 1;
    int L = 0;
    for (int i = 2; i <= N; i++, L = 1 - L)
        for (int s = 0; s <= i * (i - 1) / 2; s++) {
            strings[L][s] = ( strings[1 - L][ module(s - i + 1) ] +
                            strings[1 - L][s + i - 1] ) % MOD;
        }

    out << strings[1 - L][S] << '\n';

    return 0;
}