CATALAN – SPOJ

const
  fi='';
  fo='';
  maxn=21;
var
  f : array[1..2*maxn,0..2*maxn] of int64;
  i,j,n : longint;
  x,kq2 : array[1..2*maxn] of longint;
  res,kq1,k : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to 2*n+1 do read(x[i]);
    readln(k);
    close(input);
  end;
function tinh(i,tr : longint) : int64;
  var sl : int64;
  begin
    if f[i,tr]>-1 then exit(f[i,tr]);
    if i>2*n+1 then
      if tr=0 then exit(1) else exit(0);
    sl := 0;
    sl := sl + tinh(i+1,tr+1);
    if tr>0 then
    sl := sl + tinh(i+1,tr-1);
    f[i,tr] := sl;
    exit(sl);
  end;
procedure truyvan1;
  begin
    kq1 := 0;
    for i:=2 to 2*n do
      if x[i]>x[i-1] then
        if x[i]-2>=0 then
          kq1 := kq1 + tinh(i+1,x[i]-2);
    inc(kq1);
  end;
procedure lankq(i : longint);
  begin
    if i>2*n then exit;
    if kq2[i-1]-1>=0 then
      begin
        if k>tinh(i+1,kq2[i-1]-1) then
          begin
            k:=k-tinh(i+1,kq2[i-1]-1);
            kq2[i] := kq2[i-1]+1;
            lankq(i+1);
            exit;
          end;
      end
      else
        begin
          kq2[i] := kq2[i-1]+1;
          lankq(i+1);
          exit;
        end;
    kq2[i] := kq2[i-1]-1;
    lankq(i+1);
  end;
procedure truyvan2;
  begin
    kq2[1] := 0;
    lankq(2);
  end;
procedure process;
  begin
    fillchar(f,sizeof(f),255);
    res := tinh(2,0);
    f[1,0] := res;
    truyvan1;
    truyvan2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    //writeln(res);
    writeln(kq1);
    for i:=1 to 2*n+1 do write(kq2[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

const fi=''; fo=''; maxn=21; var f : array[1..2*maxn,0..2*maxn] of int64; i,j,n : longint; x,kq2 : array[1..2*maxn] of longint; res,kq1,k : int64; procedure enter; begin assign(input,fi);reset(input); readln(n); for i:=1 to 2*n+1 do read(x[i]); readln(k); close(input); end; function tinh(i,tr : longint) : int64; var sl : int64; begin if f[i,tr]>-1 then exit(f[i,tr]); if i>2*n+1 then if tr=0 then exit(1) else exit(0); sl := 0; sl := sl + tinh(i+1,tr+1); if tr>0 then sl := sl + tinh(i+1,tr-1); f[i,tr] := sl; exit(sl); end; procedure truyvan1; begin kq1 := 0; for i:=2 to 2*n do if x[i]>x[i-1] then if x[i]-2>=0 then kq1 := kq1 + tinh(i+1,x[i]-2); inc(kq1); end; procedure lankq(i : longint); begin if i>2*n then exit; if kq2[i-1]-1>=0 then begin if k>tinh(i+1,kq2[i-1]-1) then begin k:=k-tinh(i+1,kq2[i-1]-1); kq2[i] := kq2[i-1]+1; lankq(i+1); exit; end; end else begin kq2[i] := kq2[i-1]+1; lankq(i+1); exit; end; kq2[i] := kq2[i-1]-1; lankq(i+1); end; procedure truyvan2; begin kq2[1] := 0; lankq(2); end; procedure process; begin fillchar(f,sizeof(f),255); res := tinh(2,0); f[1,0] := res; truyvan1; truyvan2; end; procedure print; begin assign(output,fo);rewrite(output); //writeln(res); writeln(kq1); for i:=1 to 2*n+1 do write(kq2[i],' '); close(output); end; begin enter; process; print; end.