Cod sursa(job #1142565)

Utilizator andreiagAndrei Galusca andreiag Data 13 martie 2014 22:34:38
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <iostream>
#include <fstream>
#include <string.h>

using namespace std;
const int Nmax = 260;
const int Smax = 260*130;

const int P = 194767;

int D[Nmax][Smax];
inline int abs(int x) { return x > 0 ? x : -x; }

int answer(int n, int s) { // se garanteaza s >= 0;
    if (2*s > n*(n-1)) return 0;
    if (n == 1) return (s == 0);
    if (D[n][s] > -1) return D[n][s];
    return D[n][s] = (answer(n-1, abs(s - (n-1))) +       // daca primul pas e  1
                      answer(n-1, abs(s + (n-1))) ) % P;  // daca primul pas e -1
}

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) { g << 0 << endl; return 0; }
    memset(D, -1, sizeof(D));
    int ans = answer(N, S);
    g << ans << endl;

    return 0;
}