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.

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

def func(lv, id):
    sz = 4 * 2 ** lv - 3
    num = 2 * 2 ** lv - 1
    mid = (sz + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num - 1) / 2 + 1
    if id == sz:
        return num
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz:
        return func(lv - 1, id - (sz - 3) / 2 - 2) + (num - 1) / 2 + 1

print func(N, X)

Solution (Python):
N, X = map(int, input().split())
pat = [1 for _ in range(N+1)]
mai = [1 for _ in range(N+1)]
for i in range(1, N+1):
  mai[i] = 2 * mai[i-1] + 3
  pat[i] = 2 * pat[i-1] + 1

def cnt_pat(x, n):
  if n == 0:
    return 1
  if x == 1:
    return 0
  if x <= mai[n] // 2:
    return cnt_pat(x-1, n-1)
  if x == mai[n] // 2 + 1:
    return pat[n-1] + 1
  if x < mai[n]:
    return pat[n-1] + 1 + cnt_pat(x-mai[n]//2-1, n-1)
  if x == mai[n]:
    return pat[n]
  
print(cnt_pat(X, N))

Solution (Python):
N, X = map(int, raw_input().split())

sz = [4 * 2 ** i - 3 for i in range(N + 1)]
num = [2 * 2 ** i - 1 for i in range(N + 1)]

def func(lv, id):
    mid = (sz[lv] + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num[lv] - 1) / 2 + 1
    if id == sz[lv]:
        return num[lv]
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz[lv]:
        return func(lv - 1, id - sz[lv - 1] - 2) + num[lv - 1] + 1

print func(N, X)

Solution (Python):


from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

sz = [1] * (N + 1)
num = [1] * (N + 1)

for i in range(N):
    sz[i + 1] = sz[i] * 2 + 3
    num[i + 1] = num[i] * 2 + 1

def func(lv, id):
    mid = (sz[lv] + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num[lv] - 1) / 2 + 1
    if id == sz[lv]:
        return num[lv]
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz[lv]:
        return func(lv - 1, id - sz[lv - 1] - 2) + num[lv - 1] + 1

print func(N, X)

Solution (Python):







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

def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    elif x<=a[n-1]+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))

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

a = [1]
p = [1]

for i in range(N):
  a.append(2*a[i] + 3)
  p.append(2*p[i] + 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)
  elif X == 2 + a[N-1]:
    return p[N-1]+1
  elif X <= 2 + 2*a[N-1]:
    return p[N-1]+1+f(N-1, X-2-a[N-1])
  else:
    return 2*p[N-1]+1
  
print(f(N, X))

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


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

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

print(f(N, X))

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


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

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

print(f(N, X))

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

Solution (Python):
N, X = [int(_) for _ in input().split()]

def calc(n, x, cache = {}):
    if n == 1:
        return min(max(x - 1, 0), 3)
    else:
        plen = 2 * 2 ** n - 3
        if x == 1:
            return 0
        elif x >= 4 * 2 ** n - 3:
            return 2 * 2 ** n - 1
        elif x < 2 + plen:
            return calc(n - 1, x - 1)
        elif x == 2 + plen:
            return calc(n - 1, x - 1) + 1
        else:
            return 2 ** n + calc(n - 1, x - 2 - plen)

result = calc(N, X)

print(result)

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

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

def patty(n, x):
    if n == 0:
        if x > 0 : return 1
        else : return 0
    elif x <= 1 + l[n-1]:
        return patty(n-1,x-1)
    else:
        return p[n-1] + 1 + patty(n-1, x-2-l[n-1])

print(patty(N,X))

Solution (Python):
N, X = [int(_) for _ in input().split()]


def calc(n, x, cache = {}):
    
    key = (n, x)
    if key in cache:
        return cache[key]
    if n == 1:
        if x < 2:
            result = 0
        elif x < 5:
            result = x - 1
        else:
            result = 3
    else:
        plen = 2 * 2 ** n - 3
        if x == 1:
            result = 0
        elif x < 2 + plen:
            result = calc(n - 1, x - 1)
        elif x == 2 + plen:
            result = calc(n - 1, x - 1) + 1
        else:
            result = calc(n - 1, plen) + 1 + calc(n - 1, x - 2 - plen)
    
    cache[key] = result
    return result

result = calc(N, X)

print(result)

Solution (Python):



import sys


sys.setrecursionlimit(10 ** 6)

read_list_int = lambda: list(map(int, sys.stdin.readline().strip().split(' ')))


def f(n: int, x: int, a: list, p: list):
    if n == 0 and x == 0:
        return 0
    elif n == 0:
        return 1
    elif x == 1:
        return 0
    elif 1 < x <= 1 + a[n-1]:
        return f(n-1, x-1, a, p)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif 2+a[n-1] < x <= 2+2*a[n-1]:
        return p[n-1]+1+f(n-1, x-(2+a[n-1]), a, p)
    elif x == 3 + 2*a[n-1]:
        return 2*p[n-1]+1


def solution(n: int, x: int):
    a = [1] + [0]*n
    p = [1] + [0]*n

    for i in range(1, n+1):
        a[i] = 2*a[i-1] + 3
        p[i] = 2*p[i-1] + 1
    
    return f(n, x, a, p)



def main():
    n, x = read_list_int()
    print(solution(n, x))


if __name__ == '__main__':
    main()

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

thickness=[1]
for i in range(1,n):
    thickness.append(2*thickness[i-1]+3)
patty=[1]
for i in range(1,n):
    patty.append(2*patty[i-1]+1)


def pattyCnt(n,x):
    if n==0:
        return 0 if x<=0 else 1
    elif x<=1+thickness[n-1]:
        return pattyCnt(n-1,x-1)
    else:
        return patty[n-1]+1+pattyCnt(n-1,x-2-thickness[n-1])

print(pattyCnt(n,x))

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

Solution (Python):
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))

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

layer = [1]
num_of_P = [1]
result = 0

for _ in range(N-1):
    layer.append(layer[-1] * 2 + 3)
    num_of_P.append(num_of_P[-1] * 2 + 1)

layer.append(layer[-1] * 2 + 3)

while num_of_P:
    if layer[-1] // 2 + 1 > X:
        X -= 1
    else:
        X -= layer[-1] // 2 + 1
        result += num_of_P[-1] + 1

    del layer[-1]
    del num_of_P[-1]

print(result if X < 1 else result+1)

Solution (Python):
N, X = (int(x) for x in input().split())

a = [1]
p = [1]

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

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

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


def search(level, eat_num):
    if level == 0:
        if eat_num <= 0:
            return 0
        else:
            return 1

    elif eat_num == 1:
        return 0

    elif 1 < eat_num <= pow(2, level + 1) - 2:
        return search(level - 1, eat_num - 1)

    elif eat_num == pow(2, level + 1) - 1:
        return pow(2, level)

    elif pow(2, level + 1) - 1 < eat_num <= pow(2, level + 2):
        return pow(2, level) + search(level - 1, eat_num - (pow(2, level + 1) - 1))

    elif X == pow(2, level + 2) + 1:
        return pow(2, level + 1) - 1

    else:
        return pow(2, level + 1) - 1


print(search(level=N, eat_num=X))

Solution (Python):
import numpy as np

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

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


def f(N, X):
    ai_1 = a_list[N-1]
    if N == 1:
        if 1 <= X and X <= 4:
            out = X - 1
        else: 
            assert X == 5
            out = 3
    elif X == 1:
        out = 0
    elif 2 <= X and X <= 1+ai_1:
        out = f(N-1, X-1)
    elif X == 2 + ai_1:
        out = p_list[N-1] + 1
    elif 3 + ai_1 <= X and X <= 2 + 2*ai_1:
        out = p_list[N-1] + 1 + f(N-1, X - 2 - a_list[N-1])
    else:
        assert X == 3+ 2*ai_1
        out = p_list[N]
    return out


print(f(N, X))

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

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

print(f(N,X))

Solution (Python):
N,X=map(int, raw_input().split())

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




X-=1

def f(N,X):


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

print f(N,X)

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

def ct(n, x):
    
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x == L[n]//2+1:
        return P[n-1]+1
    elif x == L[n]:
        return P[n]
    elif x < L[n]//2+1:
        return ct(n-1,x-1)
    else:
        return P[n-1] + 1 + ct(n-1,x-(L[n]//2+1))

L = [1]
for i in range(50):
    L.append(L[-1]*2+3)
P = [1]
for i in range(50):
    P.append(P[-1]*2+1)

print(ct(N, X))

Solution (Python):
n, x = [int(i) for i in input().split()]








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


def search(i, x):
    pat = 0
    if i == 0:
        
        return 1
    
    elif x == 0:
        
        return 0
    
    elif x == 1 + int((length[i][0] - 3) / 2):
        
        return length[i - 1][1] + 1
    
    elif x == length[i][0] - 1:
        
        return length[i][1]
    
    elif x < 1 + int((length[i][0] - 3) / 2):
        pat = search(i - 1, x - 1)
    
    elif x > 1 + int((length[i][0] - 3) / 2):
        pat = length[i - 1][1] + 1\
              + search(i - 1, x - 2 - int((length[i][0] - 3) / 2))
    
    return pat


print(search(n, x - 1))

Solution (Python):
def bottom(lv, k):
    if lv == 0:
        return 1
    n = 2**(lv+2) - 3
    prev_pat = 2**lv-1
    if k-1 == 0:
        return 0
    elif 0 < k-1 < n//2:
        return bottom(lv-1, k-1)
    elif k-1 == n//2:
        return prev_pat + 1
    elif n//2 < k-1 < n-1:
        return prev_pat + 1 + bottom(lv-1, k-(n//2+1))
    elif k-1 == n-1:
        return 2**(lv+1)-1

n, k = list(map(int, input().split()))

print(bottom(n, k))

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

def b_size(N): 
    return 2 ** (N+2) - 3

def p_num(N): 
    return 2 ** (N+1) - 1

def f(level, X):
    if X == 0:
        return 0

    if level == 0:
        return 1

    if X <= b_size(level-1)+1:
        return f(level-1, X-1)
    else:
        return p_num(level-1) + f(level-1, X-b_size(level-1)-2) + 1

print(f(n, x))

Solution (Python):
a = []
p = []

def dfs (x,i,depth):

    if i <= 1:
        
        if x == 0:
            return 0
        elif x == 1:
            return 1
        elif x == 2:
            return 2
        elif x >= 3:
            return 3
    else:
        
        if a[i]//2 < x  :
            x = x - a[i]//2 - 1
            
            return (p[i-1] + 1) + dfs(x,i-1,depth)
        elif a[i]//2 == x :
            
            return (1 + dfs(x-1,i-1,depth))
        else:
            
            if x - 1 <= 0:
                return 0
            else:
                return dfs(x-1,i-1,depth)

def ddff (i,depth):
    if i >= depth-1:
        return 'bpppb'
    else:
        return 'b' + ddff(i+1,depth) + 'p' + ddff(i+1,depth) + 'b'
 
n,x = map(int,input().split())

for i in range(n+1):
    p.append(2**(i+1)-1)
    b = 2**(i+1)-2
    a.append(p[i] + b)


r = dfs(x-1,n,n)
print(r)

Solution (Python):
import math

def burger_size(n):
    return 2**(n + 2) - 3

def num_of_patty(n):
    return 2**(n + 1) - 1

def calc(n, x):
    if n == 0:
        return 1
    if x <= n:
        return 0
    if x == burger_size(n):
        return num_of_patty(n)
    
    center = math.floor((burger_size(n) + 1) / 2)
    if x < center:
        return calc(n - 1, x - 1)
    elif x > center:
        return num_of_patty(n - 1) + 1 + calc(n - 1, x - burger_size(n - 1) - 2)
    else:
        return num_of_patty(n - 1) + 1

n, x = [int(i) for i in input().split()]
print(calc(n, x))

Solution (Python):
N, X = [int(elem) for elem in input().split()]
h_burger = [None] * (N + 1)
p_burger = [None] * (N + 1)
h_burger[0] = 1
p_burger[0] = 1
for i in range(1, N + 1):
    h_burger[i] = h_burger[i - 1] * 2 + 3
    p_burger[i] = p_burger[i - 1] * 2 + 1


def num_patties(l, x):
    if l == 0:
        return 1 if x >= 1 else 0
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patties(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return p_burger[l - 1] + 1
        else:
            return p_burger[l - 1] + 1 \
                + num_patties(l - 1, x - h_burger[l - 1] - 2)


print(num_patties(N, X))

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

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

"""
B a[i-1] P a[i-1] B

"""
def solve(level, under):
  
  if level == 0:
    return 1 if under > 0 else 0
  elif under == 0:
    return 0
  elif under <= a[level-1] + 1:
    return solve(level-1, under-1)
  elif under == a[level-1] + 2:
    return p[level-1] + 1
  elif under == a[level]:
    return p[level]
  else:
    return p[level-1]+1 + solve(level-1, under - (a[level-1]+2))
  
print(solve(N,X))

Solution (Python):
from functools import lru_cache

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

bargar = [1 for i in range(N+1)]
for i in range(1, N+1):
    bargar[i] = bargar[i-1]*2 +3

patie = [1 for i in range(N+1)]
for i in range(1, N+1):
    patie[i] = patie[i-1]*2 +1


def rec(dim):
    global X
    if dim==0:
        X -= 1
        if X >= 0: return 1
        else: return 0

    res = 0; X -= 1
    if X==0: return res

    if X>=bargar[dim-1]: res += patie[dim-1]; X-= bargar[dim-1]
    else: res += rec(dim-1)
    if X==0: return res

    res += 1; X -= 1
    if X==0: return res

    if X>=bargar[dim-1]: res += patie[dim-1]; X-= bargar[dim-1]
    else: res += rec(dim-1)
    if X==0: return res

    X -= 1
    if X==0: return res
    return res

print(rec(N))

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

a = [1]
p = [1]

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

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

print(dp(N, X))

Solution (Python):
N,X=map(int,input().split())
a=[2**(i+2)-3 for i in range(N+1)]
p=[2**(i+1)-1 for i in range(N+1)]
def ans(n,x):
    if n==0:
        return 1
    if x<=1:
        return 0
    elif x<=2**(n+1)-2:
        return ans(n-1,x-1)
    elif x==2**(n+1)-1:
        return p[n-1]+1
    elif x<=2**(n+2)-4:
        return p[n-1]+1+ans(n-1,x+1-2**(n+1))
    else:
        return p[n]
print(ans(N,X))

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

C = [0]*(N+1)
D = [0]*(N+1)
C[0] = D[0] = 1
for i in range(1, N+1):
    C[i] = 2*C[i-1] + 1
    D[i] = 2*D[i-1] + 3

ans = 0
for i in range(N-1, -1, -1):
    if X == 0:
        break
    X -= 1
    if X < D[i]:
        continue
    ans += C[i]
    X -= D[i]
    if X == 0:
        break
    X -= 1; ans += 1
    if X < D[i]:
        continue
    X -= D[i]
    ans += C[i]
    if X == 0:
        break
    X -= 1
print(ans)

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

a, p = [None] * (N + 1), [None] * (N + 1)
a[0], p[0] = 1, 1
for i in range(1, N + 1):
    a[i], p[i] = 2 * a[i - 1] + 3, 2 * p[i - 1] + 1


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

print(f(N, X))

Solution (Python):
N,X = map(int,input().split())
alist = [2**(i+2)-3 for i in range(N+1)]
cntlist = [2**(i+1)-1 for i in range(N+1)]
cnt = 0
i = 0

while True:
    i += 1
    if X <= N-i+1:
        break
    elif alist[-i] - (N-i+1) <= X:
        cnt += cntlist[-i]
        break
    elif alist[-i]//2 +1 < X: 
        cnt += cntlist[-i]//2 +1
        X -= alist[-i]//2 +1
    elif X == alist[-i]//2 +1: 
        cnt += cntlist[-i]//2 + 1
        break
    elif X < alist[-i]//2 +1: 
        X -= 1

print(cnt)

Solution (Python):
N, K = map(int, input().split())

c = [1, 1]
t = [c]
for i in range(N):
    c = [c[0] * 2 + 3, c[1] * 2 + 1]
    t.append(c)

def f(cur, n, k):
    u = t[n-1]
    m = u[0] + 2
    if k == t[n][0]:
        return cur + t[n][1]
    elif k == 1:
        return cur
    elif k == m:
        return cur + 1 + u[1]
    elif k > m:
        return f(cur + 1 + u[1], n - 1, k - u[0] - 2)
    elif m > k:
        return f(cur, n - 1, k - 1)
print(f(0, N, K))

Solution (Python):
N,X=map(int,input().split())
PILE=[2**(i+2)-3 for i in range(51)]
def dp(n,x):
   if x==0:
       return 0
   if n==0 and x==1:
       return 1
   if n>=1:
       bp=PILE[n-1]
       if x==1:
           return 0
       elif x<=1+bp:
           return dp(n-1,x-1)
       elif x==2+bp:
           return 1+dp(n-1,bp)
       elif 2+bp<x<=2+2*bp:
           return 1+dp(n-1,bp)+dp(n-1,x-2-bp)
       elif x==3+2*bp:
           return 1+dp(n-1,bp)*2

print(dp(N,X))

Solution (Python):
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 fn(N, X):
    
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= 1+a[N-1]:
        return fn(N-1, X-1)
    else:
        return p[N-1] + 1 + fn(N-1, X-2-a[N-1])


print(fn(N, X))

Solution (Python):
n, x = map(int,input().split())
def ABC115D(n,x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x >= 2**(n+1)-1:
        return ABC115D(n-1,x-2**(n+1)+1) + 2**n
    else:
        return ABC115D(n-1,x-1)
print(ABC115D(n,x))

Solution (Python):
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 1 if x>=1 else 0
    if x==1:
        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))

Solution (Python):
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

a = [1]
p = [1]
for _ in range(51):
    a.append(3 + 2*a[-1])
    p.append(1 + 2*p[-1])

def burger(level: int, x: int):
    if level == 0:
        if x <= 0:
            return 0
        else:
            return 1
    
    if x == 1:
        return 0
    
    elif 1 < x <= 1+a[level-1]:
        return burger(level-1, x-1)
    
    elif x == 2+a[level-1]:
        return p[level-1] + 1
    
    elif 2+a[level-1] < x <= 2+2*a[level-1]:
        return p[level-1] + 1 + burger(level-1, x-1-a[level-1]-1)
    
    elif x == 3+2*a[level-1]:
        return 2*p[level-1] + 1
    
n,x = li()    
print(burger(n,x))

Solution (Python):
def feed_runrun(burger_dimension, appetite):
    if appetite == 0:
        return 0

    burger_size = 2 ** (burger_dimension + 2) - 3
    amount_of_p = 2 ** (burger_dimension + 1) - 1

    if appetite == burger_size:
        return amount_of_p
    if appetite < burger_size:
        return feed_runrun(burger_dimension - 1, appetite - 1)
    if appetite > burger_size:
        return amount_of_p + 1 \
               + feed_runrun(burger_dimension, appetite - burger_size - 1)


n, x = map(int, input().split())
print(feed_runrun(n, x))

Solution (Python):
def f(n,x):
  if x == 0:
    return 0
  elif n == 0:
    return 1
  elif x <= 2**(n+1)-2:
    return f(n-1,x-1)
  elif x == 2**(n+1)-1:
    return 2**n
  elif x<= 2**(n+2)-4:
    return f(n-1,x-(2**(n+1)-1))+2**n
  else:
    return 2**(n+1)-1

n,x = map(int,input().split())
print(f(n,x))

Solution (Python):
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))

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

atusa=[1]
Pkosu=[1]
for i in range(n):
  atusa.append(atusa[-1]*2+3)
  Pkosu.append(Pkosu[-1]*2+1)

def getPkosu(level,num):
  
  if level==0 and num==0:
    return 0
  elif level==0 and num==1:
    return 1
  elif num==1 or num==0:
    return 0
  elif num <= atusa[level-1]+1:
    return getPkosu(level-1,num-1)
  elif num == atusa[level-1]+2:
    return Pkosu[level-1]+1
  elif num <= atusa[level-1]*2+2:
    return Pkosu[level-1]+getPkosu(level-1,num-(2+atusa[level-1]))+1
  else:
    return Pkosu[level-1]*2+1

print(getPkosu(n,x))

Solution (Python):
import sys
import collections
import itertools
import math
import re
from collections import deque

MOD = 10 ** 9 + 7

N, X = [int(x) for x in input().split()]
ML = 51
P = [0] * ML
A = [0] * ML

P[0] = 1
A[0] = 1

for i in range(1, ML):
    P[i] = 2 * P[i - 1] + 1
    A[i] = 2 * A[i - 1] + 3


def f(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 1

    r = 0
    if x <= 1 + A[n - 1]:
        r = f(n - 1, x - 1)
    elif x == 2 + A[n - 1]:
        r = 1 + P[n - 1]
    else:
        r = f(n - 1, x - 2 - A[n - 1]) + 1 + P[n - 1]

    return r


r = f(N, X)

print(r)

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

a = [0, 1]
b = [0, 1]
for i in range(n):
    a.append(a[i + 1] * 2 + 1)
    b.append(b[i + 1] * 2 + 3)

if b[-1] == x:
    print(a[-1])
    exit()

ans = 0
left = 0
mid = int(b[-1] / 2)
right = b[-1] - 1
i = len(b) - 1
while i > 0:
    if mid + 1 == x:
        ans += a[i - 1] + 1
        break
    elif mid < x:
        ans += a[i - 1] + 1
        left = mid + 1
        mid = mid + int((right - mid) / 2)
        right = right - 1
    else:
        right = mid - 1
        mid = mid - int((mid - left) / 2)
        left = left + 1
    i = i - 1

print(ans)

Solution (Python):
def do(level,x):
    if x<=0: 
        return 0
    elif x>=whole[level]: 
        return patty[level]
    
    x-=1 
    res=0 
    if x>=whole[level-1]+1: 
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1]+[0]*50
patty=[1]+[0]*50
for i in range(1,n+1):
    whole[i]=whole[i-1]*2+3
    patty[i]=patty[i-1]*2+1
print(do(n,x))

Solution (Python):
def do(level,x):
    if x<=0: 
        return 0
    elif x>=whole[level]: 
        return patty[level]
    
    x-=1 
    res=0 
    if x>=whole[level-1]+1: 
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645, 4294967293, 8589934589, 17179869181, 34359738365, 68719476733, 137438953469, 274877906941, 549755813885, 1099511627773, 2199023255549, 4398046511101, 8796093022205, 17592186044413, 35184372088829, 70368744177661, 140737488355325, 281474976710653, 562949953421309, 1125899906842621, 2251799813685245, 4503599627370493]
patty=[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247]
print(do(n,x))

Solution (Python):
def do(level,x):
    if x<=0: 
        return 0
    elif x>=whole[level]: 
        return patty[level]
    
    x-=1 
    res=0 
    if x>=whole[level-1]+1: 
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1]+[0]*50
patty=[1]+[0]*50
for i in range(1,n+1):
    whole[i]=whole[i-1]*2+3
    patty[i]=patty[i-1]*2+1
res=0
print(do(n,x))

Solution (Python):
N,X = map(int,input().split())
B = [-1 for i in range(51)]
P = [-1 for i in range(51)]

def buns(L):
    if L == 0:
        B[L] = 0
        return B[L]
    else:
        if B[L] == -1:
            B[L] = buns(L-1)*2 + 2
            return B[L]
        else:
            return B[L]

def patty(L):
    if L == 0:
        P[L] = 1        
        return P[L]
    else:
        if P[L] == -1:
            P[L] = patty(L-1)*2 + 1
            return P[L]
        else:
            return P[L]


buns(N)
patty(N)
memo = [B[i] + P[i] for i in range(51)]

def func(L,X):

    if L == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= memo[L-1]+1:
        return func(L-1,X-1)
    else :
        return P[L-1] + 1 + func(L-1,X-2-memo[L-1])


print(func(N,X))

Solution (Python):
def do(level,x):
    if x<=0:
        return 0
    elif x>=j[level]:
        return k[level]
    res=0
    x-=1
    if x>=j[level-1]+1:
        x-=j[level-1]+1
        res+=k[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
j=[1]+[0]*50
k=[1]+[0]*50
for i in range(1,n+1):
    j[i]=j[i-1]*2+3
    k[i]=k[i-1]*2+1
res=0
print(do(n,x))

Solution (Python):
def do(level,x):
    if x<=0:
        return 0
    if level==0:
        return 1
    res=0
    x-=1
    if x>j[level-1]:
        x-=j[level-1]+1
        res+=k[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
j=[1]+[0]*50
k=[1]+[0]*50
for i in range(1,n+1):
    j[i]=j[i-1]*2+3
    k[i]=k[i-1]*2+1
res=0
print(do(n,x))

Solution (Python):
import math
N,X = list(map(int, input().split()))
cnt = 0
for i in range(N, 0, -1):
  t = math.pow(2, i + 1) - 2
  if X >= t * 2:
    cnt += t + 1
    break
  elif X >= t:
    cnt += t / 2
    X -= t
    if X > 1:
      cnt += 1
      X -= 1
    elif X == 1:
      cnt += 1
      break
    else:
      break
  else:
    if X > 1:
      X -= 1
    else:
      break
print(int(cnt))

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

size, p_num = [1], [1]
for i in range(1, N + 1):
    size.append(size[i - 1] * 2 + 3)
    p_num.append(p_num[i - 1] * 2 + 1)


def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + size[n - 1]:
        return f(n - 1, x - 1)
    else:
        return p_num[n - 1] + 1 + f(n - 1, x - 2 - size[n - 1])  


print(f(N, X))

Solution (Python):
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))

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

p, a = [1], [1]

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

def f(n,x):
    if x <= 0:
        return 0
    else:
        if n <= 0:
            return min(x, 3)
        else:
            if x > a[n]:
                return p[n] + 1 + f(n-1, x-2-a[n])
            elif x == a[n]:
                return p[n]
            else:
                return f(n-1,x-1)

print(f(n,x))