Cod sursa(job #2130753)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 13 februarie 2018 21:19:13
Problema 1-sir Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.74 kb
#include <cstdio>

const int MAXN = 1 << 8;
#define MOD 194767

int d[2][((MAXN * (MAXN - 1)) >> 1) + 1];

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

int main() {
  FILE *fin, *fout;
  int n, s;
  fin = fopen("1-sir.in", "r");
  fscanf(fin, "%d%d", &n, &s);
  fclose(fin);
  fout = fopen("1-sir.out", "w");
  if (((n * (n - 1)) >> 1) < s || s < -((n * (n - 1)) >> 1)) {
    fprintf(fout, "0\n");
  } else {
    int p;
    d[0][0] = p = 1;
    for (int i = 2; i <= n; ++i) {
      for (int j = 0; j <= (i * (i - 1)) >> 1; ++j) {
        d[p][j] = (d[p ^ 1][abs(j - i + 1)] + d[p ^ 1][abs(j + i - 1)]) % MOD;
      }
      p ^= 1;
    }
    fprintf(fout, "%d\n", d[p ^ 1][s]);
  }
  fclose(fout);
  return 0;
}