CATALAN - Dãy số Catalan
Tác giả: flashmt
Ngôn ngữ: Pascal
var n:shortint;
b,a:array[0..30] of byte;
f:array[0..30,-1..16] of longint;
k,re:longint;
procedure rf;
var i:byte;
begin
readln(n);
for i:=0 to 2*n do read(b[i]);
readln;
readln(k);
end;
procedure pr;
var i,j,t:shortint;
begin
fillchar(f,sizeof(f),0);
f[0,0]:=1;
for i:=1 to n do
begin
t:=i mod 2;
for j:=0 to i div 2 do
f[i,j*2+t]:=f[i-1,j*2+t-1]+f[i-1,j*2+t+1];
end;
for i:=n+1 to 2*n do
begin
t:=i mod 2;
for j:=0 to (2*n-i) div 2 do
f[i,j*2+t]:=f[i-1,j*2+t-1]+f[i-1,j*2+t+1];
end;
a[0]:=0; a[2*n]:=0; a[1]:=1; a[2*n-1]:=1;
j:=1;
for i:=2*n-2 downto 2 do
begin
if k>f[i,j-1] then
begin
k:=k-f[i,j-1];
inc(j);
a[i]:=j;
end
else
begin
dec(j);
a[i]:=j;
end;
end;
re:=0; t:=1;
for i:=2*n-2 downto 2 do
begin
j:=b[2*n-i];
if j>t then re:=re+f[i,t-1];
t:=j;
end;
end;
procedure wf;
var i:byte;
begin
writeln(re+1);
for i:=2*n downto 0 do write(a[i],' ');
end;
begin
rf;
pr;
wf;
end.