CATALAN - Dãy số Catalan

Tác giả: hieult

Ngôn ngữ: C++

#include <stdio.h>
//#include <conio.h>
long n,k,i,j,min,kq,tong,C[41],r[41],F[41][41];
long mini(long x,long y)
  {
  if(x>y) return y;
  else return x;
  }
main()
{
scanf("%ld",&n);
n=2*n+1;
for(i=1;i<=n;i++)
  scanf("%ld",&C[i]);
scanf("%ld",&k);
F[n][0]=1;
F[n-1][1]=1;
for(i=n-2;i>=1;i--)
  {
  if(i%2==0) j=1;
  else j=0;
  while(j<=min)
    {
    min=mini(n-i,i-1);
    if(j>0)
      F[i][j]=F[i+1][j-1];
    if(j+1<=n-(i+1))
      F[i][j]=F[i][j]+F[i+1][j+1];
    j=j+1;
    }
  }
for(i=3;i<=n-2;i++)
  {
  if(C[i]>C[i-1]&&C[i-1]>0)
    kq=kq+F[i][C[i-1]-1];
  }
printf("%ld\n",kq+1);
r[1]=0;
r[2]=1;
for(i=3;i<=n;i++)
  {
  min=mini(n-i,i-1);
  if(r[i-1]+1>min)
    r[i]=r[i-1]-1;
  else if(r[i-1]==0)
    r[i]=1;
  else
    {
    if(k>F[i][r[i-1]-1])
      {
      r[i]=r[i-1]+1;
      k=k-F[i][r[i-1]-1];
      }
    else r[i]=r[i-1]-1;
    }
  }
for(i=1;i<=n;i++)
  printf("%ld ",r[i]);
//getch();
}                
            

Download