## Editorial for TAPN

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

const maxn=31;
var n,t,i:longint;
re,m:int64;
d:array[1..31] of longint;
c,a:array[0..31,-1..31] of int64;

procedure init;
var i,j:longint;
begin
fillchar(a,sizeof(a),0);
for i:=1 to maxn do
begin
a[i,0]:=1;
a[i,i]:=1;
end;
for i:=2 to maxn do
for j:=1 to i-1 do
a[i,j]:=a[i-1,j]+a[i-1,j-1];
fillchar(c,sizeof(c),0);
for i:=1 to maxn do
begin
c[i,0]:=1;
for j:=1 to i do
c[i,j]:=c[i,j-1]+a[i,j];
end;
end;

procedure find;
var i,pos,j:longint;
begin
fillchar(d,sizeof(d),0); pos:=0;
if m=1 then exit;
if m=c[n,n] then
begin
for i:=1 to n do d[i]:=1;
exit;
end;
for i:=0 to n-1 do
if m>c[n,i] then pos:=i else break;
m:=c[n,pos+1]-m+1;
inc(pos);
for i:=n-1 downto 1 do
begin
if m>a[i,pos] then
begin
d[n-i]:=1;
m:=m-a[i,pos];
dec(pos);
end
else d[n-i]:=0;
end;
d[n]:=pos;
end;

begin
init;
repeat
find;
re:=1;
for i:=1 to n do
if d[i]=0 then re:=re*2+1
else re:=re*3+1;
writeln(re);
until eof;
end.


#### Code mẫu của RR

//Written by RR
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>

#define MAXN 32
#define FOR(i,a,b)  for(typeof(a) i=a; i<=b; i++)
#define FORD(i,a,b) for(typeof(a) i=a; i>=b; i--)

using namespace std;

long n,bit[MAXN];
long long m,res,c[MAXN][MAXN];

void init() {
c[0][0]=1;
FOR(i,1,MAXN-1) {
c[i][0]=1;
FOR(j,1,MAXN-1)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
}

void solve() {
long k=0;
while (c[n][k]<m) {
m-=c[n][k];
k++;
}
m=c[n][k]-m+1;
long len=n;
FOR(i,1,n) {
if (c[len-1][k]>=m) bit[i]=0;
else {m-=c[len-1][k]; bit[i]=1; k--; }
len--;
}
res=1;
FOR(i,1,n)
if (bit[i]==0) res=res*2+1;
else res=res*3+1;
cout<<res<<"\n";
}

int main() {
#ifdef DEBUG
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
init();
while (scanf("%ld %lld",&n,&m)==2)
solve();
return 0;
}


#### Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
long long KQ(long long a[],long long n)
{
long long T=1;
for(long i=1;i<=n;i++)
{
if(a[i]==0)
T=T*2+1;
else T=T*3+1;
}
return T;
}
main()
{
long long C[33][33],a[33],n,m,t;
for(long i=0;i<=32;i++)
for(long j=0;j<=32;j++)
C[i][j]=0;
for(long i=0;i<=32;i++)
C[0][i]=1;
for(long i=1;i<=32;i++)
for(long j=0;j<=i;j++)
C[j][i]=C[j][i-1]+C[j-1][i-1];
while(scanf("%lld %lld",&n,&m)>0)
{
for(long i=1;i<=n;i++)
a[i]=0;
for(long i=0;i<=n;i++)
{
//printf("%lld ",m);
if(m<=C[i][n])
{
//printf("0 ");
t=i;
break;
}
else m=m-C[i][n];
}
//printf("1 ");
long u=n-1;
for(long i=t;i>=1;i--)
{
while(1)
{
if(m<=C[i-1][u])
{
a[n-u]=1;
u--;
break;
}
else
m=m-C[i-1][u];
u--;
}
}
printf("%lld\n",KQ(a,n));
}
//getch();
}


#### Code mẫu của khuc_tuan

#include <cstdio>
#include <set>
using namespace std;

int main() {
int n;
long long m;
long long F[32][32];

memset( F, 0, sizeof(F));
F[0][0] = 1;
for(int i=1;i<32;++i) {
for(int j=0;j<=i;++j) {
F[i][j] = F[i-1][j];
if(j>0) F[i][j] += F[i-1][j-1];
}
}
while(scanf("%d%lld", &n, &m) != EOF) {
long long r = 1;
for(int i=0;i<=n;++i) {
if(m>F[n][i]) m -= F[n][i];
else {
int pos = n;
int sl = i;
while(pos > 0) {
if(sl > 0 && m <= F[pos-1][sl-1]) {
r = r * 3 + 1;
--sl;
--pos;
}
else {
if(sl>0) m -= F[pos-1][sl-1];
r = r * 2 + 1;
--pos;
}
}
break;
}
}
printf("%lld\n", r);
}
return 0;
}