Cod sursa(job #1142611)

Utilizator andreiagAndrei Galusca andreiag Data 13 martie 2014 23:16:55
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.76 kb
#include <fstream>
#include <string.h>

using namespace std;
const int Smax = 260*130;
const int P = 194767;

int D[2][Smax];

inline int abs(int x) { return x > 0 ? x : -x; }

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

    int N, S;
    f >> N >> S;

    S = abs(S);
    if (S > Smax || 2*S > N*(N-1)) { g << 0 << endl; return 0; }

    memset(D, 0, sizeof(D));
    int c = 0;  // randul curent;
    D[1][0] = 1;
    for (int n = 2; n <= N; n++) {
        //for (int s = 0; s < Smax; s++) D[c][s] = 0;
        for (int s = 0; 2*s <= n*(n-1); s++) {
            D[c][s] = (D[1-c][abs(s-(n-1))] +
                       D[1-c][abs(s+(n-1))] ) % P;
        }
        c = 1 - c;
    }
    int answer = D[N%2][S];
    g << answer << endl;

    return 0;
}