## Editorial for Tháp Hà Nội

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

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;

int main()
{
int m,n,i,j,k;
unsigned long long f[65][65];
fr(i,1,64) f[1][i]=1;
fr(i,2,64) f[i][3]=f[i-1][3]*2+1;
fr(i,2,64)
fr(j,4,64)
if (i<=j-1) f[i][j]=2*i-1;
else
{
f[i][j]=f[i][j-1];
fr(k,1,i-1) f[i][j]=min(f[i][j],f[i-k][j-1]+f[k][j]*2);
}
while (cin >> n)
{
cin >> m;
cout << f[n][m] << endl;
}
return 0;
}


program chntower_dp;
uses    math;
const   fi='';
const   a:array[3..64] of int64 =(0,0,12582907,458745,65527,18421,7155,3825,2287,1645,1195,937,743,645,547,465,431,397,363,329,295,285,275,265,255,245,235,225,215,205,195,189,187,185,183,181,179,177,175,173,171,169,167,165,163,
161,159,157,155,153,151,149,147,145,143,141,139,137,135,133,131,129);
var     f:array[0..66,0..66] of qword;
check:array[0..66,0..66] of boolean;
m,n:longint;
inp:text;

procedure init;
var     i:longint;
begin
fillchar(f,sizeof(f),0);
fillchar(check,sizeof(check),false);
for i:=3 to 65 do
begin
f[0,i]:=0;
check[0,i]:=true;
f[1,i]:=1;
check[1,i]:=true;
end;

end;

function dp(n,p:longint):qword;
var     k:longint;
//res:int64;

begin

if check[n,p] then exit(f[n,p]);
f[n,p]:=high(qword);
if p = 3 then
begin
f[n,p]:=2*dp(n-1,3)+1;
exit(f[n,p]);
check[n,p]:=true;
end;
for k:=0 to n-1 do
begin
if f[n,p]>2*dp(k,p)+dp(n-k,p-1)
then f[n,p]:=2*dp(k,p)+dp(n-k,p-1);

end;
//f[n,p]:=res;
check[n,p]:=true;
exit(f[n,p]);
end;

begin
assign(inp,fi);
reset(inp);
init;
while not eof(inp) do
begin
{if n = 64 then
begin
if m=3 then write('18446744073709551615')
else if m=4 then write(18433)
else write(a[m]);
exit;
end;  }

writeln(dp(n,m));
end;
end.


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

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--)
#define REP(i,a) for(int i=0,_a=(a); i<_a; i++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

unsigned ll f[66][66];

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);

FOR(r,1,64) FOR(n,1,64) f[n][r] = 10001110001110001110ULL;

f[1][2] = 1;
FOR(r,3,64) {
f[1][r] = 1;
FOR(n,2,64) {
f[n][r] = 2*f[1][r] + f[n-1][r-1];
FOR(k,2,n-1)
f[n][r] = min(f[n][r], 2*f[k][r] + f[n-k][r-1]);
}
}
f[64][3] = 2*f[63][3] + 1;
int n, k;
while (cin >> n >> k)
cout << f[n][k] << endl;
return 0;
}


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

#include <stdio.h>
//#include <conio.h>

int main()
{
unsigned long long f[65][65],min=1;
int n,k,a[65];

for(int i = 1;i<=63;i++) min = min*2+1;
for(int i = 0;i<=64;i++)
for(int j = 0;j<=64;j++)
f[i][j]=0;
for(int j = 3;j<=64;j++)
{
for(int i =1;i<=j-2;i++)
a[i]=0;
f[1][j]=1;
for(int i = 2;i<=64;i++)
{
int flag = 0;
unsigned long long Min = min;
for(int t=1;t<=j-2;t++)
{
if(f[a[t]+1][j-t+1]-f[a[t]][j-t+1]<Min)
{
Min = f[a[t]+1][j-t+1]-f[a[t]][j-t+1];
flag = t;
}
}
//if(j==3 &&i<10)printf("i=%d   Min=%llu   flag=%d\n",i,Min,flag);
f[i][j]=f[i-1][j]+2*Min;
a[flag]++;

}
}

while(scanf("%d %d",&n,&k)>0)
printf("%llu\n",f[n][k]);
// getch();
}