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.

Download