Tower of Hanoi II | tower of Hanoi 4 columns

Hanoi II| Hanoi 4 column

Problem Description

The classical Hanoi Tower problem often exists as a recursive classical example . Maybe someone doesn't know the story of the tower of Hanoi problem . The tower of Hanoi comes from a story in Indian legend , God made three diamond pillars when he created the world , On a column, they are stacked in order of size from bottom to top 64 A golden disk . God ordered Brahman to rearrange the disc on another post in order of size from below . And stipulate , You can't enlarge a disc on a small disc , Only one disc can be moved between the three pillars at a time . There is a prophecy that , When this is done, the universe will be destroyed in a flash . Some people believe that Brahmans are still moving the disc all the time . Okay , Of course, this legend is not believable , Nowadays, Hanoi Tower exists more as a toy .Gardon I received a Hanoi Tower toy as a birthday gift .
　　Gardon He is afraid of trouble （ Okay , Is a lazy person ）, It is obvious that 64 It's difficult to move the plates one by one until all the plates reach the third pillar , therefore Gardon Decided to make a small mistake , He found another exactly the same post , Move all the dishes to the third pillar faster through this pillar . The following question is ： When Gardon Used in a game N When you have a plate , How many times does he need to move them to the third pillar ？ Obviously , When there is no fourth pillar , The solution to the problem is 2^N-1, But now with the help of this pillar , How much should it be ？

Input

Contains multiple sets of data , One line per data , It's the number of plates N(1<=N<=64).

Output

For each set of data , Output a number , The minimum number of moves required to reach the target .

Sample Input

1
3
12

Sample Output

1
5
81

Be careful

If this topic doesn't open unsigned long long Will always be wa.

#include<bits/stdc++.h>
using namespace std;

#define int unsigned long long // If this topic doesn't open ull You can't make it (tu...)

int f3[70],f4[70];
void init(){
    
    f3[0] = 0;
    for (int i = 1; i <= 64; ++i) {
    
        f3[i] = 2 * f3[i - 1] + 1;
    }
    memset(f4,0x7f,sizeof f4);f4[0] = 0;
    for (int i = 1; i <= 64; ++i) {
    
        for (int j = 0; j <= i; ++j) {
    
            f4[i] = min(f4[i],2 * f4[j] + f3[i - j]);
        }
    }
}
signed main(){
    
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    init();
    int n;
    while (cin>>n){
    
        cout<<f4[n]<<"\n";
    }
    return 0;
}