Cod sursa(job #213400)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 9 octombrie 2008 18:10:02
Problema Dame Scor 25
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.21 kb
#include <stdio.h>

int st[1000], n, fol[1000];

int bkt();
int succesor(int k);
int valid(int k);
void tipar();
int abs(int x);

int main()
{
  int t;
  freopen("dame.in", "r", stdin);
  freopen("dame.out", "w", stdout);
  scanf("%d", &n);
  if (n>3)
  {
    printf("%d\n", n);
    t=bkt();
  }//if
  else
	  if ((n==2)||(n==1))
		  printf("1\n1 1\n");
	  else
		  printf("2\n1 1\n2 3\n");
  return 0;
}//main

int bkt()
{
  int k=0;
  fol[0]=1;
  while (k>=0)
  {
    if (succesor(k))
    {
      if (valid(k))
      {
	     if (k==(n-1))
	     {
	       tipar();
	       return 0;
	     }//if
	     else
	       k++;
      }//if
    }//if
    else
       k--;
  }//while
  return 0;
}//bkt

int succesor(int k)
{
  fol[st[k]]=0;
  st[k]++;
  while ((st[k]<n)&&((fol[st[k]])==1))
  {
    st[k]++;
  }//if
  if ((st[k]<=n)&&(fol[st[k]]==0))
  {
    fol[st[k]]=1;
	 return 1;
  }//if
  else
  {
    st[k]=0;
    return 0;
  }//else
}//succesor

int valid(int k)
{
  int i;
  for (i=0; i<k; i++)
    if ((abs(i-k))==(abs(st[i]-st[k])))
      return 0;
  return 1;
}//valid

void tipar()
{
  int i;
  for (i=0; i<n; i++)
    printf("%d %d\n", i+1, st[i]);
}//tipar

int abs(int x)
{
  if (x>=0)
    return x;
  else
    return -1*x;
}//abs