Cod sursa(job #8644)

Utilizator cristi8Constantin-Cristian Balas cristi8 Data 25 ianuarie 2007 11:51:30
Problema 1-sir Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 0.75 kb
#include <stdio.h>
#define NMAX 260

int n, S;

int lev;
int s;
int st[NMAX];
int sol;

void back() {
  int i;
  if(lev == n) {
    if(s == S)
      sol++;
    //{
      //for(i = 1; i <= n; i++)
      //  printf("%d ", st[i]);
      //printf("\n");
    //}
    return;
  }
  if((n - lev) * (n - lev + 1) / 2 + (n - lev) * st[lev] < S - s)
    return;
  lev++;
  for(i = 1; i >= -1; i -= 2) // 1 si -1
  {
    st[lev] = st[lev-1] + i;
    s += st[lev];
    back();
    s -= st[lev];
  }
  lev--;
}

int main()
{	
  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;
  }
  st[1] = 0;
  lev = 1;
  back();
  printf("%d\n", sol%194767);
  return 0;
}