Cod sursa(job #8739)

Utilizator cristi8Constantin-Cristian Balas cristi8 Data 25 ianuarie 2007 15:04:12
Problema 1-sir Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 0.8 kb
#include <stdio.h>
#define NMAX 257
#define SMAX (64*257+1)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MOD 194767

int n, S;
int a[SMAX][2];

#define ccrt(j) ((j)%2)
#define cnxt(j) (((j)+1)%2)

int main()
{	
  int i, j, s;
  freopen("1-sir.in", "r", stdin);
  freopen("1-sir.out", "w", stdout);
  scanf("%d%d", &n, &S);
  if(S < 0)
    S = -S;
  if((n/2)%2 != S%2) {
    printf("0\n");
    return 0;
  }
  S = ((n*(n-1))/2 - S) / 2;
  if(S <= 0) {
    printf("%d\n", S < 0 ? 0 : 1);
    return 0;
  }
  n--;

  for(j = MIN(n, S-1); j > 0; j--)
  {
    a[j][ccrt(j)] = 1;
    if(j + 1 <= n)
      a[j+1][cnxt(j)] = 1;
    for(i = j+1; i <= S; i++)
    {
      a[i][ccrt(j)] = a[i][cnxt(j)];
      a[i][ccrt(j)] = (a[i][ccrt(j)] + a[i-j][cnxt(j)]) % MOD;
    }
  }

  s = a[S][ccrt(1)];
  printf("%d\n", s);
  return 0;
}