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();
}