Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

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.

Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long LL;

#define sz(a) (int((a).size()))
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); i != _e; ++i)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N 20

#define F(i,j) (i >= 0 && i <= n+n && j >= 0 && j <= n ? f[i][j] : 0)
LL f[N+N][N]; int n;
int a[N+N], pos;
bool finish;

void dfs(int i, int lo, int hi) {
    printf("%d %d %d\n", i, lo, hi);
    if( lo > hi || lo > pos || hi < pos ) return;
    if( i == n+n ) {
        if( lo == hi && lo == pos ) {
            printf("0");
            fo(i,1,n+n) printf(" %d", a[i]); putchar(10);
            finish = 1;
        }
    } else {
        a[i] = a[i-1]-1; dfs(i+1, lo, F(i,a[i-1]-1));
        if(finish) return;
        a[i] = a[i-1]+1; dfs(i+1, F(i,a[i-1]-1), hi);
        if(finish) return;
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen( "input.txt", "r", stdin );
    //freopen( "output.txt", "w", stdout );
#endif
    scanf("%d",&n);
    f[n+n][0] = 1;
    repd(i,n+n) fo(j,0,n) f[i][j] = F(i+1,j+1) + F(i+1,j-1);
    //fo(j,0,n) {fo(i,0,n+n) printf("%3lld ", f[i][j]); putchar(10);}
    rep(i,n+n+1) scanf("%d",a+i); 
    pos = 0;
    fo(i,1,n+n)
        if(a[i] > a[i-1]) pos += F(i,a[i]-2);
        else pos += F(i,a[i]-1);
    printf("%d\n", pos+1);
    scanf("%d",&pos); 
    a[0] = 0; a[1] = 1;
    fo(i,2,n+n) {
        if(pos <= F(i,a[i-1]-1)) {
            a[i] = a[i-1]-1;
        } else {
            pos -= F(i,a[i-1]-1);
            a[i] = a[i-1]+1;
        }
    }
    printf("%d", a[0]);
    fo(i,1,n+n) printf(" %d", a[i]); putchar(10);
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define REP(i, a, b) for(int i = (a); i <=(b); i++)
#define FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 50;
using namespace std;
int n, kth;
int a[N], f[N][N];

int cnt;
void naive(int i) {
    if (i > n) {
        if (a[n] == 1) {
            cout << ++cnt << "  ";
            REP(i, 1, n) cout << a[i] << ' ';
            cout << endl;
        }
        return;
    }
    if (a[i - 1] >= 1) {
        a[i] = a[i - 1] - 1;
        naive(i + 1);
    }
    a[i] = a[i - 1] + 1;
    naive(i + 1);
}

int main() {
    ios :: sync_with_stdio(0); cin.tie(0);
    cin >> n; n <<= 1;
    REP(i, 0, n) cin >> a[i];
    cin >> kth;
    n--;
    f[n][1] = 1;
    REPD(i, n, 2) REP(j, 0, n) if (f[i][j]) {
        //cout << i << ' ' << j << ' ' << f[i][j] << endl;
        f[i - 1][j + 1] += f[i][j];
        if (j) f[i - 1][j - 1] += f[i][j];
    }
    int ans = 0;
    REP(i, 1, n) {
        FOR(j, 0, a[i])
        if (abs(a[i - 1] - j) == 1)
            ans += f[i][j];
    }
    cout << ans + 1 << endl;
    a[1] = 1;
    //naive(2);
    REP(i, 2, n) {
        if (a[i - 1] == 0) {
            a[i] = 1;
            continue;
        }
        if (f[i][a[i - 1] - 1] < kth) {
            kth -= f[i][a[i - 1] - 1];
            a[i] = a[i - 1] + 1;
        }
        else a[i] = a[i - 1] - 1;
    }
    REP(i, 0, n + 1) cout << a[i] << ' ';
    return 0;
}

Code mẫu của RR

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.

Code mẫu của hieult

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

Code mẫu của ll931110

Program CATALAN;
        Const
                input  = '';
                output = '';
        Var
                F: array[1..40,-1..20] of longint;
                a: array[1..40] of longint;
            n,c,k: longint;
               fo: text;

Procedure init;
          Var
                fi: text;
                 i: longint;
          Begin
                Assign(fi, input);
                        Reset(fi);
                                Readln(fi, n);
                                c:= 2 * n + 1;

                                For i:= 1 to c do read(fi, a[i]);
                                Readln(fi);
                                Readln(fi, k);
                Close(fi);
          End;

Procedure catalan;
          Var
                i,j: longint;
          Begin
                Fillchar(F, sizeof(F), 0);
                F[c,0]:= 1;

                For i:= c - 1 downto 1 do
                        For j:= 0 to n do F[i,j]:= F[i + 1,j + 1] + F[i + 1,j - 1];
          End;

Procedure solve1;
          Var
                val,i: longint;
          Begin
                val:= 1;

                For i:= 2 to c do
                        if a[i] > a[i - 1] then val:= val + F[i,a[i] - 2];

                Writeln(fo, val);
          End;

Procedure solve2;
          Var
                i,num: longint;
          Begin
                Write(fo, 0, ' ');

                num:= 0;

                For i:= 2 to 2 * n do
                    Begin
                        if k > F[i,num - 1] then
                                        Begin
                                                k:= k - F[i,num - 1];
                                                inc(num);
                                        End
                        else dec(num);

                        Write(fo, num, ' ');
                    End;

                Writeln(fo, 0);
          End;

Begin
        Assign(fo, output);
                Rewrite(fo);
                        init;
                        catalan;
                        solve1;
                        solve2;
        Close(fo);
End.

Code mẫu của khuc_tuan

import java.io.*;
import java.util.*;
import java.math.*;
import static java.lang.Integer.parseInt;

class Process {
    BigInteger[][] f;
    public void run(int n, int[] a, BigInteger b) {
        f=new BigInteger[2*n+1][2*n+1];
        f[2*n][0] = BigInteger.valueOf(1);
        for(int i=1;i<f[2*n].length;++i) f[2*n][i] = BigInteger.ZERO;
        for(int i=2*n-1;i>=0;--i) {
            for(int j=0;j<f[i].length;++j) {
                f[i][j] = BigInteger.ZERO;
                if(j>0) f[i][j] = f[i][j].add(f[i+1][j-1]);
                if(j<f[i].length-1) f[i][j] = f[i][j].add(f[i+1][j+1]);
            }
        }
        BigInteger c=BigInteger.ONE;
        for(int i=1;i<2*n;++i) {
            if(a[i]-2>=0 && a[i-1]<a[i]) c=c.add(f[i][a[i]-2]);
        }
        System.out.println(c);
        int[] r=new int[2*n+1];
        r[1]=1;
        for(int i=2;i<2*n;++i) {
            if( r[i-1]-1>=0) {
                if(b.compareTo(f[i][r[i-1]-1]) > 0) {
                    b=b.subtract(f[i][r[i-1]-1]);
                    r[i]=r[i-1]+1;
                }
                else {
                    r[i]=r[i-1]-1;
                }
            }
            else {
                r[i]=r[i-1]+1;
            }
        }
        for(int i=0;i<r.length;++i) { System.out.print(r[i]); System.out.print(' '); }
        System.out.println();
    }
}

public class Main {
    public static void main(String[] Args) throws Exception {
        BufferedReader kb=new BufferedReader(new InputStreamReader(System.in));
        int n = parseInt(kb.readLine());
        StringTokenizer st=new StringTokenizer(kb.readLine());
        int[] a=new int[2*n+1];
        for(int i=0;i<a.length;++i) a[i]=parseInt(st.nextToken());
        BigInteger b=new BigInteger(kb.readLine());
        new Process().run(n,a,b);
    }
}