/ 
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
とある世界では、今日はクリスマスです。
高羽氏のパーティで、彼は多次元バーガーを作ることにしました。レベル L バーガー (L は 0 以上の整数) とは次のようなものです。
- レベル 0 バーガーとは、パティ 1 枚である。
- レベル L バーガー (L \geq 1) とは、バン 1 枚、レベル L-1 バーガー、パティ 1 枚、レベル L-1 バーガー、バン 1 枚、をこの順に下から積み重ねたものである。
例えば、パティを P、バンを B で表すと、レベル 1 バーガーは BPPPB (を 90 度回転したもの)、レベル 2 バーガーは BBPPPBPBPPPBB といった見た目になります。
高羽氏が作るのはレベル N バーガーです。ダックスフンドのルンルンは、このバーガーの下から X 層を食べます (パティまたはバン 1 枚を 1 層とします)。ルンルンはパティを何枚食べるでしょうか？
制約
- 1 \leq N \leq 50
- 1 \leq X \leq ( レベル N バーガーの層の総数 )
- N, X は整数である。
入力
入力は以下の形式で標準入力から与えられる。
N X
出力
レベル N バーガーの下から X 層に含まれるパティの枚数を出力せよ。
入力例 1
2 7
出力例 1
4
レベル 2 バーガー (BBPPPBPBPPPBB) の下から 7 層にはパティが 4 枚含まれます。
入力例 2
1 1
出力例 2
0
レベル 1 バーガーの一番下の層はバンです。
入力例 3
50 4321098765432109
出力例 3
2160549382716056
レベル 50 バーガーは層の数が 32 ビット整数に収まらない程度に分厚いです。
Score : 400 points
Problem Statement
In some other world, today is Christmas.
Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:
- A level-0 burger is a patty.
- A level-L burger (L \geq 1) is a bun, a level-(L-1) burger, a patty, another level-(L-1) burger and another bun, stacked vertically in this order from the bottom.
For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.
The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?
Constraints
- 1 \leq N \leq 50
- 1 \leq X \leq ( the total number of layers in a level-N burger )
- N and X are integers.
Input
Input is given from Standard Input in the following format:
N X
Output
Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.
Sample Input 1
2 7
Sample Output 1
4
There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB).
Sample Input 2
1 1
Sample Output 2
0
The bottom-most layer of a level-1 burger is a bun.
Sample Input 3
50 4321098765432109
Sample Output 3
2160549382716056
A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.