CATALAN - Dãy số Catalan

Tác giả: RR

Ngôn ngữ: Pascal

var
  f:array[-1..50,-1..50] of longint;
  res,pos,n,gh,i,j:longint;
  a:array[0..50] of longint;

begin
  read(n);
  f[1,0]:=1;
  for i:=2 to n shl 1+1 do
    begin
      if i<=n+1 then inc(gh) else dec(gh);
      for j:=0 to gh do
        f[i,j]:=f[i-1,j+1]+f[i-1,j-1];
    end;

  i:=n shl 1+1; j:=0; read(a[1]); res:=1;
  for pos:=2 to n shl 1+1 do
    begin
      read(a[pos]); dec(i);
      if a[pos]>j then inc(res,f[i,j-1]);
      j:=a[pos];
    end;
  writeln(res);

  fillchar(a,sizeof(a),0);
  read(res); a[n shl 1+1]:=0; dec(res);
  i:=n shl 1+1; j:=0;
  for pos:=2 to n shl 1+1 do
    begin
      dec(i);
      if res<f[i,j-1] then dec(j)
      else begin dec(res,f[i,j-1]); inc(j); end;
      a[pos]:=j;
    end;

  for i:=1 to n shl 1+1 do
    write(a[i],' ');
  writeln;
end.

Download