Codeforces Round #287 (Div. 2) C 構造

連結：戳這裡

C. Guess Your Way Out! time limit per test1 second memory limit per test256 megabytes inputstandard input outputstandard output Amr bought a new video game "Guess Your Way Out!". The goal of the game is to find an exit from the maze that looks like a perfect binary tree of height h. The player is initially standing at the root of the tree and the exit from the tree is located at some leaf node.

Let's index all the leaf nodes from the left to the right from 1 to 2h. The exit is located at some node n where 1 ≤ n ≤ 2h, the player doesn't know where the exit is so he has to guess his way out!

Amr follows simple algorithm to choose the path. Let's consider infinite command string "LRLRLRLRL..." (consisting of alternating characters 'L' and 'R'). Amr sequentially executes the characters of the string using following rules:

Character 'L' means "go to the left child of the current node";

Character 'R' means "go to the right child of the current node";

If the destination node is already visited, Amr skips current command, otherwise he moves to the destination node;

If Amr skipped two consecutive commands, he goes back to the parent of the current node before executing next command;

If he reached a leaf node that is not the exit, he returns to the parent of the current node;

If he reaches an exit, the game is finished.

Now Amr wonders, if he follows this algorithm, how many nodes he is going to visit before reaching the exit?

Input

Input consists of two integers h, n (1 ≤ h ≤ 50, 1 ≤ n ≤ 2h).

Output

Output a single integer representing the number of nodes (excluding the exit node) Amr is going to visit before reaching the exit by following this algorithm.

Examples

input

1 2

output

2

input

2 3

output

5

input

3 6

output

10

input

10 1024

output

2046

Note

A perfect binary tree of height h is a binary tree consisting of h + 1 levels. Level 0 consists of a single node called root, level h consists of 2h nodes called leaves. Each node that is not a leaf has exactly two children, left and right one.

Following picture illustrates the sample test number 3. Nodes are labeled according to the order of visit.

題意：

深度為h的二叉樹，現在要從節點1通過LRLRLRLRLR....這樣的路徑走到标号為(2^h+n-1)的葉子節點

這裡其實就是最後一層葉子結點從左往右數第n個，需要多少步。走過節點跳過

思路：

暴力去周遊這樣的路徑肯定會T

那麼考慮可不可以少計算一點，因為如果n在目前結點的左邊但是卻往右走，可以直接加上右邊的節點個數轉走左邊

同理，如果n在目前結點的右邊但是卻往左走。可以直接加上左邊的節點個數轉走右邊

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#include<bitset>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
typedef long double lb;
#define INF (1ll<<60)-1
#define Max 1e9
using namespace std;
int h;
ll n;
ll a[55];
int main(){
    a[0]=1;
    for(int i=1;i<=50;i++) a[i]=a[i-1]*2LL;
    scanf("%d%I64d",&h,&n);
    ll ans=1;
    int f=0; /// L->0 R->1
    while(n && h){
        if(f==0){
            if(n-a[h-1]>0) {
                ans+=a[h];
                n-=a[h-1];
                h--;
                f=0;
            } else {
                h--;
                f=1;
                ans++;
            }
        } else {
            if(n-a[h-1]>0){
                n-=a[h-1];
                h--;
                f=0;
                ans++;
            } else {
                ans+=a[h];
                f=1;
                h--;
            }
        }
        ///printf("%I64d %I64d\n",n,ans);
    }
    printf("%I64d\n",ans-1);
    return 0;
}