Cod sursa(job #1393527)

Utilizator addy01adrian dumitrache addy01 Data 19 martie 2015 15:39:13
Problema 1-sir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <iostream>
#include <fstream>

using namespace std;

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

const int MAXN = 256 + 10;
const int MOD = 194767;

int N, S;
int Best[2][MAXN * MAXN];
//Best[i][j] = cate siruri d-alea cu i elemente si cu suma j

int main()
{
    in >> N >> S;
    if (S < 0)
        S = -S;

    int Max = N * (N - 1) / 2;

    if (S > Max){
        out << 0;

        return 0;
    }

    int i, j;
    int now;
    int a, b;

    Best[1][0] = 1;
    for (i = 2; i <= N; i ++){
        now = i % 2;

        for (j = 1; 2 * j <= i * (i - 1); j ++){
            a = j - (i - 1);
            b = j + (i - 1);

            if (a < 0)
                a = -a;

            if (a <= Max)
                Best[now][j] = (Best[now][j] + Best[!now][a]) % MOD;
            if (b <= Max)
                Best[now][j] = (Best[now][j] + Best[!now][b]) % MOD;
        }
    }

    out << Best[N % 2][S];

    return 0;
}