Problem:


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.



Sample input:
2 7


Sample output:
4

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)

"""考え方
L0 : P
L1 : BPPPB
L2 : BBPPPBPBPPPBB
L3 : BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
L4 : ...

・レベルが1上がると、Pの数は2倍+1になる
・レベルが1上がると、総数は2倍+3になる


レベルiバーガーの厚さ（層の総数）をa_iとする
レベルiバーガーに含まれるパティの総数をp_iとする
「レベルNバーガーの下からX層に含まれるパティの枚数」をf(N,X)とする。

・N = 0のとき
f(0,X) = 1

・N >= 1のとき
f(N-1, Y)がわかると仮定すると、

(1) X = 1のとき、f(N,X) = 0 (一番下のバンだけ)

(2) 1 < X <= 1 + a_{i-1} のとき、f(N,X) = f(N-1, X-1)

i=2のとき、L2のときで
BBPPPB PBPPPBB
BPPPBB|ここまでのとき

(3) X = 2 + a_{i-1}のとき、f(N,X) = p_{i-1}+1
???


https://www.youtube.com/watch?v=1ONpCPN-IR8
"""
def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる


    def _dfs(depth, x):
        """ レベルdepthバーガーの、下からX層に含まれるパティの枚数を返す """
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[depth-1]:
            # 一番下のパン + その上のレベル N-1 バーガー + その上のパティ
            return _dfs(depth-1, x-1)
        else:
            # (前略) + その上のパティ + その上のレベル N-1 バーガーの下から x-2-As[depth-1]層
            return Ps[depth-1] + 1 + _dfs(depth-1, x-2-As[depth-1])

    ans = _dfs(N, X)

    print(ans)


def solve2():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


def solve3():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    # dp[i][x] := レベルiバーガーの下からx層に含まれているパティの総数
    dp = [[0]*(X+1) for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 1

    for i in range(N+1):
        for x in range(X+1):
            median = (As[i]+1)//2
            if x < median:
                dp[i][x] = dp[i-1][x-1]
            elif x == median:
                dp[i][x] = Ps[i-1] + 1
            else:
                dp[i][x] = Ps[i-1] + 1 + dp[i-1][x-median]

    print(dp[N][X])



if __name__ == "__main__":
    solve3()

Submission status: Runtime Error

Solution code:
N, X = map(int, input().split())

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def f(N, X): 
if N == 0:
    return 0 if X <= 0 else 1
elif X <= 1 + a[N-1]:
    return f(N-1, X-1)
else:
    return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N, X))

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(1000000)

def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)
        Ps.append(Ps[i]*2 + 1)


    def _dfs(depth, x):
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[N-1]:
            return _dfs(N-1, x-1)
        else:
            return Ps[N-1] + 1 + _dfs(N-1, x-2-As[N-1])

    ans = _dfs(N, X)

    print(ans)

if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
N, X = [int(i) for i in input().split()]
b = "P"
for i in range(N):
    b = "B" + b + "P" + b + "B"

b_eat = b[:X]
print(b_eat.count("P"))

Submission status: Runtime Error

Solution code:
N, X = map(int, input().split())

S = 'P'
while N > 0:
    S = 'B' + S + 'P' + S + 'B'
    N -= 1
print(S[:X].count('P'))

Submission status: Runtime Error

Solution code:
#14:22
n,k = map(int,input().split())
whole = [1]
patty = [1]
for _ in range(n):
  whole.append(whole[-1] * 2 + 3)
  patty.append(patty[-1] * 2 + 1)
ans = 0
rest = k
for i in range(n,-1,-1):
  if i == 0:
    ans += [0,1,2,3,3][rest]
    rest = 0
  elif rest < whole[i]:
    rest -= 1
  elif rest == whole[i]:
    rest -= whole[i]
    ans += patty[i]
  elif rest == whole[i] + 1:
    rest -= whole[i] + 1
    ans += patty[i] + 1
  else:
    rest -= whole[i] + 2
    ans += patty[i] + 1
  if rest == 0:
    print(ans)
    break

Submission status: Runtime Error

Solution code:
#14:22
n,k = map(int,input().split())
whole = [1]
patty = [1]
for _ in range(n):
  whole.append(whole[-1] * 2 + 3)
  patty.append(patty[-1] * 2 + 1)
ans = 0
rest = k
for i in range(n,-1,-1):
  if i == 0:
    ans += [0,0,1,2,3][rest]
    rest = 0
  elif rest < whole[i]:
    rest -= 1
  elif rest == whole[i]:
    rest -= whole[i]
    ans += patty[i]
  elif rest == whole[i] + 1:
    rest -= whole[i] + 1
    ans += patty[i] + 1
  else:
    rest -= whole[i] + 2
    ans += patty[i] + 1
  if rest == 0:
    print(ans)
    break

Submission status: Runtime Error

Solution code:
 N, X = map(int, input().split())
2
3 a, p = [1], [1]
4 for i in range(N):
5 a.append(a[i] * 2 + 3)
6 p.append(p[i] * 2 + 1)
7
8 def f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
9 if N == 0:
10 return 0 if X <= 0 else 1
11 elif X <= 1 + a[N-1]:
12 return f(N-1, X-1)
13 else:
14 return p[N-1] + 1 + f(N-1, X-2-a[N-1])
15
16 print(f(N, X))

Submission status: Runtime Error

Solution code:
# ABC115D - Christmas
def burger(n):
    x = "P"
    for i in range(n):
        x = "B" + x + "P" + x + "B"
    return x


def main():
    N, X = tuple(map(int, input().split()))
    n_burger = burger(N)[:X]
    ans = n_burger.count("P")
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
def burg(lev,x):
  if lev == 0:
    return x>0
  if x == 1:
    return 0
  if 1 < x <= h[lev-1]+1:
    return burg(lev-1,x-1)
  if x ==  h[lev-1]+2:
    return p[lev-1] + 1
  if h[lev-1]+3 <= x <= h[lev-1]*2 + 2:
    return p[lev-1] + 1 + burg(lev-1,x-(h[lev-1]+2))
  if x >= h[lev]:
    return paty[lev]

n,x = map(int, input().split())
h = [1]*(n+2)
p = [1]*(n+2)
for i in range(1,n+2):
  h[i] = h[i-1]*2 + 3
  p[i] = p[i-1]*2 + 1
print(burg(n,x))

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())

l = [0]*(n+1)
l[0] = 1
for i in range(1,n+1):
  l[i] = l[i-1]*2+3

p = [0]*(n+1)
p[0] = 1
for i in range(1,n+1):
  p[i] = p[i-1]*2+1
  
ans = 0  
def bts(a,b):
  global ans
  if b = 1:
    ans += 0
  elif 1 < b < l[a-1]+1:
    bts(a-1,b-1)
  elif b == l[a-1]+1:
    ans += p[a-1]
  elif b == l[a-1]+2:
    ans += p[a-1]+1
  elif l[a-1]+2 < b < l[a-1]*2+2:
    ans += p[a-1]+1
    bts(a-1,b-2-l[a-1])
  else:
    ans += p[a-1]+2

bts(n,x)
  
print(ans)

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())

a = 'P'
for i in range(1,n+1):
  a = 'B'+a+'P'+a+'B'
  
print(a[:x].count('P'))

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())

a = 'P'
for i in range(1,n):
  a = 'B'+a+'P'+a+'B'
  
print(a[:x].count('P'))

Submission status: Runtime Error

Solution code:
N,X= [int(i) for i in input().split()]
b = "P"
for i in range(N):
	b ='B' + b + 'P' + b + 'B' 
print(b[:X].count('P'))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-                                                                              

N, X = map(int, input().split())

a, p = [1], [1]

for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


def f(N, X):
    if N == 0:
	return 0 if X <= 0 else	1
    elif X <= 1	+ a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] +	1 + f(N-1, X-2-a[N-1])


print(f(N, X))

Submission status: Runtime Error

Solution code:
n,x=map(int,input().split())
B=["P"]
for i in range(1,n+1):
  b="B"+B[i-1]+"P"+B[i-1]+"B"
  B.append(b)
print(B[n][:x].count("P"))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, x = na()
bg = "P"
an = 2 ** (n+2) - 3
bn = 2 ** (n+1) - 1
if an > x:
    print(bn)
else:
    for i in range(n - 1):
        bg = "B" + bg + "P" + bg + "B"
        if len(bg) > x:
            bg = bg[:x]
    print(bg[:x].count("P"))

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, x = na()
bg = "BPPPB"
for i in range(n-1):
    bg = "B" + bg + "P" + bg + "B"
    if len(bg) > x:
        bg = bg[:x]
print(bg[:x].count("P"))

Submission status: Runtime Error

Solution code:
n,x=map(int,input().split())
a=[1]
p=[1]
for i in range(n-1):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)
def f(n,x):
  if n==0 and x==1:
    return 1
  elif n==0:
    return 0
  elif x<=1:
    return 0
  elif x<=1+a[n-]:
    return f(n-1,x-1)
  else:
    return p[n-1]+1+f(n-1,x-2-a[n-1])
print(f(n,x))

Submission status: Runtime Error

Solution code:
n,x=map(int,input().split())
a=[1]
p=[1]
for i in range(n-1):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)
def f(n,x):
  if n==0 and x=1:
    return 1
  elif n==0:
    return 0
  elif x<=1+a[n-1]:
    return f(n-1,x-1)
  else:
    return p[n-1]+1+f(n-1,x-2-a[n-1])
print(f(n,x))

Submission status: Runtime Error

Solution code:
def dp(a, b):
    if a == 1:
        if 1 <= b <= 4:
            return b-1
        else:
            return 3
    elif b == 1:
        return 0
    elif 1 < b < 2**(a+1)-1:
        return dp(a-1, b-1)
    elif b == 2**(a+1)-1:
        return dp(a-1, 2**(a+1)-3) + 1
    elif 2**(a+1)-1 < b < a:
        return dp(a-1, 2**(a+1)-3) + 1 + dp(a-1, b+1-2**(a+1))
    elif b == 2**(a+2)-3:
        return dp(a-1, 2**(a+1)-3) * 2 + 1
    
print(dp(n, x))

Submission status: Runtime Error

Solution code:
N, X = map(int, input().split())
a, p = [1], [1]
for i in range(N):
	a.append(a[i] * 2 + 3)
	p.append(p[i] * 2 + 1)

def f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
  if N == 0:
      return 0 if X = 0 else 1
  elif X <= 1 + a[N-1]:
      return f(N-1, X-1)
  else:
      return p[N-1] + 1 + f(N-1, X-2-a[N-1])
print(f(N, X))

Submission status: Runtime Error

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')
        
    # ----------------------------------
    # main

    N, X = R()
    """
    A_n = 2A_(n-1) + 3, A_0 = 1
    B_n = 2B_n-1 + 1, B_0 = 0
    """
    A = [1] * 50
    B = [1] * 50
    for i in range(1, 50):
        A[i] = 2 * A[i-1] + 3
    for i in range(1, 50):
        B[i] = 2 * B[i-1] + 1
    
    @lru_cache(maxsize=None)
    def burg(l, x):
        if x == 1:
            if l == 0:
                return 1
            return 0
        elif x <= 1 + A[l-1]:
            return 0 + burg(l-1, x-1)
        elif x == 2 + A[l-1]:
            return 1 + B[l-1]
        elif x <= 2 + 2*A[l-1]:
            return 1 + B[l-1] + burg(l-1, x-2-A[l-1])
        else:
            return B[l]
    # for i in range(1, X+1):
    #     print(N, i, ':',burg(N, i))
    print(burg(N, X))
    
    # def burger(l):
    #     if l == 0:
    #         return 'P'
    #     else:
    #         return 'B' + burger(l-1) + 'P' + burger(l-1) + 'B'
    # print(burger(3))
    
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()