Cod sursa(job #8706)

Utilizator cristi8Constantin-Cristian Balas cristi8 Data 25 ianuarie 2007 13:34:55
Problema 1-sir Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 0.79 kb
#include <stdio.h>
#define NMAX 260
#define SMAX (64*255+8)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define MOD 194767

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

int main()
{	
  int i, j, k, 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("0\n");
    return 0;
  }
  n--;

  for(i = 0; i <= S; i++)
    a[i][i] = 1;
  for(i = 0; i <= S; i++)
    for(j = MIN(i-1, n); j > 0; j--)
    {
      s = i - j; // restul sumei
      for(k = j+1; k <= n && k <= s; k++) // urmatorul termen
        a[i][j] += a[s][k];
      a[i][j] %= MOD;
    }
  
  s = 0;
  for(i = 0; i <= n; i++)
    s += a[S][i];
  printf("%d\n", s%MOD);
  return 0;
}