## Editorial for Dãy số Catalan

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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
for i:=0 to 2*n do read(b[i]);
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;
}


#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
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
if a[pos]>j then inc(res,f[i,j-1]);
j:=a[pos];
end;
writeln(res);

fillchar(a,sizeof(a),0);
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);
c:= 2 * n + 1;

For i:= 1 to c do read(fi, a[i]);
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;
}
}
BigInteger c=BigInteger.ONE;
for(int i=1;i<2*n;++i) {
}
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 {
int[] a=new int[2*n+1];
for(int i=0;i<a.length;++i) a[i]=parseInt(st.nextToken());