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):

N, X = map(int, input().split())
point = []
ans = 0

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



while a >= 1:
    if X == a :
        ans += p
        break
    elif (a+1)//2+1 <= X <= a-1:
        X -= 2+(a-3)//2
        ans += p//2 + 1
    elif  X == (a+1)//2:
        ans += p//2 + 1
        break
    elif 2 <= X <= (a+1)//2-1:
        X -= 1
    elif X == 1:
        break

    a -= 3
    a //= 2
    p -= 1
    p //= 2

    

print(ans)

Solution (Python):
line = [int(x) for x in input().strip().split()]

N = line[0]
X = line[1]


patties = [1]
buns = [0]
layers = [1]
for i in range(1, 51):
	patties.append(patties[i - 1] * 2 + 1)
	buns.append(buns[i - 1] * 2 + 2)
	layers.append(patties[i] + buns[i])

def answer(l, r, level):
	if (l > r):
		return 0
	if (l == 1 and r == layers[level]):
		return patties[level]

	mid = layers[level] // 2 + 1
	ans = 0
	if (r > mid):
		ans += 1
		ans += answer(1, layers[level - 1], level - 1)
		ans += answer(1, r - mid, level - 1)
	elif (r == mid):
		ans += 1
		ans += answer(1, layers[level - 1], level - 1)
	else:
		ans += answer(1, r - 1, level - 1)
	return ans

print(answer(1, X, N))

Solution (Python):
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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







m = {}
def f(n):
    if m.get(n) != None:
        return m[n]
    if n == 0:
        m[n] = (1, 1)
    else:
        b = f(n - 1)
        m[n] = (b[0] * 2 + 3, b[1] * 2 + 1)
    return m[n]

f(N)

def ff(n, t):
    if n == 0:
        return 0 if t <= 0 else 1
    elif t <= 1 + m[n - 1][0]:
        return ff(n - 1, t - 1)
    else:
        return m[n - 1][1] + 1 + ff(n - 1, t - 2 - m[n - 1][0])

print(ff(N, M))

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

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

ans = 0
for i in range(n, -1, -1):
    layer = l[i]
    if x >= layer:
        ans += p[i]
        break
    elif x <= 1:
        break

    half = l[i - 1] + 1
    if x > half:
        ans += 1
        ans += p[i - 1]
        x -= half
        x -= 1
    elif x <= half:
        x -= 1

print(ans)

Solution (Python):
import numpy as np
n, x = map(int, input().split())

l = np.zeros(51, dtype=np.int64)
p = np.zeros(51, dtype=np.int64)

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

ans = 0
for i in range(n, -1, -1):
    layer = l[i]
    if x >= layer:
        ans += p[i]
        break
    elif x <= 1:
        break

    half = l[i - 1] + 1
    if x > half:
        ans += 1
        ans += p[i - 1]
        x -= half
        x -= 1
    elif x <= half:
        x -= 1

print(ans)

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

print(burger(n,x))

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N, X = map(int, input().split())

    ALL = [0] * (N+1)
    PATE = [0] * (N+1)
    ALL[0] = 1
    PATE[0] = 1
    for i in range(1, N+1):
        ALL[i] = ALL[i-1] * 2 + 3
        PATE[i] = PATE[i-1] * 2 + 1
    
    def dfs(level, remain):
        if level == 0:
            return 1
        ans = 0
        
        if remain > 0:
            remain -= 1
        
        if remain > 0:
            if remain >= ALL[level - 1]:
                remain -= ALL[level - 1]
                ans += PATE[level - 1]
            else:
                ans += dfs(level - 1, remain)
                remain = 0
        
        if remain > 0:
            remain -= 1
            ans += 1
        
        if remain > 0:
            if remain >= ALL[level - 1]:
                remain -= ALL[level - 1]
                ans += PATE[level - 1]
            else:
                ans += dfs(level - 1, remain)
                remain = 0
        
        if remain > 0:
            remain -= 1
        return ans
    
    print(dfs(N, X))

if __name__ == "__main__":
    main()

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

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

def solve(N,X):
    if N == 0:
        return 0 if X <= 0 else 1

    if X <= rayers[N-1]+1:
        
        return solve(N-1, X-1)
    elif X == rayers[N-1]+2:
        
        return Ps[N-1] + 1 
    elif X > rayers[N-1]+2:
        
        return Ps[N-1] + 1 + solve(N-1, X - rayers[N-1] - 2)

print(solve(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 function(N,X):
    if N <= 0 :
        return 0 if X<= 0 else 1
    elif X <= a[N-1] + 1 :
        ret = function(N-1,X-1)
        return ret
    else:
        ret  = 1 + p[N-1]
        ret +=  function(N-1,X-a[N-1]-2)
        return ret
print(function(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:
		if x<=0:
			return 0
		else:
			return 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())
h = [1]
p = [1]
for i in range(N):
    h.append(h[i]*2+3)
    p.append(p[i]*2+1)
def f(N,X):
    if X == 1:
        if N == 0:
            return 1
        return 0
    elif 1 < X and X <= 1 + h[N-1]:
        return f(N-1,X-1)
    elif X == 2 + h[N-1]:
        return p[N-1] + 1
    elif 2 + h[N-1] < X and X <= 2 + 2 * h[N-1]:
        return p[N-1] + 1 + f(N-1,X-2-h[N-1])
    elif X == 3 + 2 * h[N-1]:
        return p[N]
print(f(N,X))

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

p = [1]
h = [1]

for i in range(50):
    p.append(1 + p[-1] * 2)
    h.append(3 + h[-1] * 2)


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

    if x <= 1 + h[n - 1]:
        return f(n - 1, x - 1)

    return p[n - 1] + 1 + f(n - 1, x - 2 - h[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):
import sys
sys.setrecursionlimit(10 ** 9)

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


def patty(l,x):
  if l == 0:
    res = 1
  else:
    if x == 1:
      res = 0
    elif 2 <= x <= L[l-1]+1:
      res = patty(l-1,x-1)
    elif x == L[l-1]+2:
      res = patty(l-1,L[l-1])+1
    elif L[l-1]+3 <= x <= L[l-1]*2+2:
      res = patty(l-1,L[l-1])+1+patty(l-1,x-L[l-1]-2)
    else:
      res = patty(l-1,L[l-1])*2+1
  return res

print(patty(N,X))

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

def main(n, x):
    if n == 0:
        if x >= 0:
            return 1
        else:
            return 0
    if x == 0:
        return 0
    if x == 2 ** (n + 1) - 2:
        return 2 ** n
    if x < 2 ** (n + 1) - 2:
        return main(n - 1, x - 1)
    if x > 2 ** (n + 1) - 2:
        return 2 ** n + main(n - 1, x - (2 ** (n + 1) - 1))
print(main(n, x))

Solution (Python):
def count(n, x):
    b1 = 1<<n
    b2 = b1<<1
    return 1 if n == 0 else \
           0 if x == 1 else \
           count(n-1, x-1) if x <b2-1 else \
           b1 if x == b2-1 else \
           count(n-1, x+1-b2)+b1 \

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

Solution (Python):
def count(n, x):
    b1 = 1<<n
    b2 = b1<<1
    return 1 if n == 0 else \
           0 if x == 1 else \
           count(n-1, x-1) if x <b2-1 else \
           b1 if x == b2-1 else \
           count(n-1, x+1-b2)+b1 \

N, X = map(int, input().split())
print(count(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())

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

def rec(n, x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    if x * 2 > h[n]:
        return 2 ** n + rec(n - 1, x - 1 - h[n] // 2)
    return rec(n - 1, x - 1)

print(rec(n, x))

Solution (Python):

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


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

print(f(n,x))

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

main()

Solution (Python):
L,X=map(int,input().split())
b=[1];p=[1]
for i in range(L):
	b.append(b[-1]*2 + 3)
	p.append(p[-1]*2 + 1)
def f(L, X):
	if L==0 or X<0:
		return 0 + (X>0)
	elif X <= 1 + b[L-1]:
		return f(L-1, X-1)
	else:
		return p[L-1] + 1 + f(L-1, X-b[L-1]-2)
print(f(L, 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):

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]  
    Ps = [1]  

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


    def _dfs(depth, x):
        """ レベルdepthバーガーの、下からX層に含まれるパティの枚数を返す """
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[depth-1]:
            
            return _dfs(depth-1, x-1)
        else:
            
            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]  
    Ps = [1]  

    for i in range(N):
        As.append(As[i]*2 + 3)  
        Ps.append(Ps[i]*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():
    As = [1]  
    Ps = [1]  

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

    


if __name__ == "__main__":
    solve2()

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())
L = [1] * n
P_num = [1] * n

for i in range(n-1):
  L[i + 1] = L[i] * 2 + 3
  P_num[i + 1] = P_num[i] * 2 + 1

def pati_num(n, x):
  if n == 0:
    if x >= 1:
      return 1
    else:
      return 0
  elif x <= 1 + L[n-1]:
    return pati_num(n-1, x-1)
  else:
    return P_num[n-1] + 1 + pati_num(n-1, x-2-L[n-1])
print(pati_num(n, x))

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

def layers(L):
  if L == 0:
    return 1
  else:
    return layers(L-1)*2+3
  
def patties(L,X):
  if L == 0:
    return 1
  elif X == 1:
    return 0
  elif X <= layers(L)//2:
    return patties(L-1,X-1)
  elif X == layers(L)//2+1:
    return layers(L-1)//2+2
  elif layers(L)//2+2 <= X <= layers(L)-1:
    return layers(L-1)//2+2+patties(L-1,X-layers(L)//2-1) 
  else:
    return layers(L)//2+1
    
print(patties(n,x))

Solution (Python):
def f(n,x):
    if n == 0:return 0 if x <= 0 else 1
    elif x <= 1+b[n-1]: return f(n-1, x-1)
    else:
        return 1+p[n-1]+f(n-1,x-2-b[n-1])

N,X=map(int,input().split())
b,p = [1 for _ in range(N+1)],[1 for _ in range(N+1)]

for i in range(1,N+1):
    b[i] = b[i-1]*2+3
    p[i] = p[i-1]*2+1
print(f(N,X))

Solution (Python):
def f(n):
    return 2**(n+2)-3
def g(n):
    return 2**(n+1)-1
def p(x,n):
    if x==1:
        return 0
    if n==1:
        if 2<=x<=4:
            return x-1
        elif x>4:
            return 3
    if x==f(n-1)+2:
        return g(n-1)+1
    if x>=2*f(n-1)+2:
        return 2*g(n-1)+1
    if x<f(n-1)+2:
        return p(x-1,n-1)
    if x<2*f(n-1)+2:
        return g(n-1)+1+p(x-f(n-1)-2,n-1)
N,X = map(int,input().split())
print(p(X,N))

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

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


def count(x, n):
    if n == 0:
        return 1 if x > 0 else 0
    if x >= (total_counts[n] + 1) // 2:
        return p_counts[n - 1] + 1 + count(x - total_counts[n - 1] - 2, n - 1)
    else:
        return count(x - 1, n - 1)


print(count(x, n))

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 p[n - 1] + 1 + f(n - 1, x - 2 - a[n - 1])


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)
    
print(f(n, x))

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

Solution (Python):
N, X = [int(i) for i in input().split()]
p = [1]
l = 1
for i in range(N):
    p.append(p[-1] * 2 + 1)
    l = 2 * l + 3
ban_l = 1
ban_r = l
pate = l//2+1
cnt = 0
for i in range(N+1):
    if X == pate:
        if pate == ban_l:
            cnt += 1
            break
        else:
            cnt += p[N-(i+1)] + 1
            break
    elif X == ban_l:
        break
    elif X < pate:
        ban_l = ban_l + 1
        ban_r = pate - 1
        pate = (pate+ban_l)//2
    elif X < ban_r:
        cnt += p[N-(i+1)] + 1
        ban_l = pate + 1
        pate = (pate+ban_r)//2
        ban_r = ban_r - 1
    else:
        cnt += p[N-i]
        break
print(cnt)

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



P = [1]
A = [1]

for i in range(1, N+1):
    P.append(2**(i+1)-1)
    A.append(2**(i+2)-3)





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,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] - (i-1):
    rest -= 1
  elif rest <= whole[i]:
    rest = 0
    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

Solution (Python):
n, x = [int(x) for x in input().split()]
def patties(n):
    return 1 if n == 0 else 2 * patties(n - 1) + 1
def layers(n):
    return 1 if n == 0 else 2 * layers(n - 1) + 3
def eat(n, x):
    if n == 0:
        return x
    else:
        if x <= layers(n - 1) + 1:
            return eat(n - 1, max(0, x - 1))
        elif x == layers(n):
            return patties(n)
        else:
            return patties(n - 1) + 1 + eat(n - 1, x - (layers(n - 1) + 1) - 1)

print(eat(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 calc(n,x):
    if n==0:
        if x <= 0:
            return 0
        else:
            return 1
    elif x <= 1 + a[n-1]:
        return calc(n-1,x-1)
    else:
        return p[n-1] + 1 + calc(n-1,x-2-a[n-1])

print(calc(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 = 1
t = 1
pdic = {}
tdic = {}
for i in range(N):
  pdic[i] = p
  tdic[i] = t
  p = 2*p+1
  t = 2*t+3
pdic[N] = p
tdic[N] = t
ans = 0
nokori = X
state = N
count = N
while True:
  while tdic[count]+state-count>nokori:
    count -= 1
    if count<0:
      break
  if count<0:
    break
  nokori -= (tdic[count]+state-count)
  state = count
  ans += pdic[count]
  if nokori==0:
    break
  nokori -= 1
  ans += 1
  if nokori==0:
    break
print(ans)

Solution (Python):
N,X = [int(x) for x in input().split()]
a,p = [1],[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)
  else:
    return p[N-1]+1+f(N-1,X-2-a[N-1])
    
print(f(N,X))

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

    return helper(N, X, a, p)

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

if __name__ == '__main__':
    print(main())

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

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

def solve(N, cur):
    if N == 0:
        return 1 if cur > 0 else 0
        
    return solve(N-1, cur-1) if cur <= (layers[N] // 2) else solve(N-1, (cur-layers[N-1])-2) + patties[N-1] + 1

print(solve(n,x))

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


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


print(f(N, X))

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

pos = X
eat = 0
for i in range(N-1, -1, -1):
    nlayer = 2 ** (i+2) - 3
    npatie = 2 ** (i+1) - 1
    if pos == 1:
        break
    elif pos <= 1 + nlayer:
        pos -= 1
        if i == 0:
            eat += 1
        continue
    elif pos == 2 + nlayer:
        eat += npatie + 1
        break
    elif pos <= nlayer * 2 + 2:
        eat += npatie + 1
        if i == 0:
            eat += 1
        pos -= nlayer + 2
    else:
        eat += npatie * 2 + 1
        break

print(eat)

Solution (Python):
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



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

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


def rec(h,i):
    if h==0:
        if i>0:
            return 1
        else:
            return 0
    else:
        if i>=l[h]-1:
            return p[h]
        elif i<=1:
            return 0
        elif 2<=i<=l[h-1]+1:
            return rec(h-1,i-1)
        elif i==l[h-1]+2:
            return p[h-1]+1
        else:
            return p[h-1]+1+rec(h-1,i-l[h-1]-2)

print(rec(N,X))

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

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

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


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

print(f(N, X))

Solution (Python):
N, X = map(int, input().split())
NLs = [1]
NPs = [1]
for L in range(1, N+1):
  NLs.append(NLs[L-1]*2+3)
  NPs.append(NPs[L-1]*2+1)

def sub(L, X):
  if L == 0:
    return X
  if X <= 1:
    return 0
  elif X <= 1+NLs[L-1]:
    return sub(L-1, X-1)
  elif X == 1+NLs[L-1]+1:
    return NPs[L-1]+1
  elif X <= 1+NLs[L-1]+1+NLs[L-1]:
    return NPs[L-1]+1+sub(L-1, X-1-NLs[L-1]-1)
  else:
    return NPs[L-1]*2+1
r = sub(N, X)
print(r)

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):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



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


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



print(f(n, x))

Solution (Python):
import sys
input = sys.stdin.readline

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

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

position = [0]*(N+1)
position[N] = X
for i in reversed(range(1,N+1)):
    if num[i-1]+2 < position[i]:
        position[i-1] = position[i] -num[i-1]-2
    else:
        if position[i]-1 < 1: break
        position[i-1] = position[i]-1
        

dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if position[i] == 0 or position[i] == 1: continue
    if position[i] < num[i-1]+2:
        dp[i] = dp[i-1]
    elif position[i] == num[i-1]+2:
        dp[i] = pnum[i-1] + 1
    else:
        dp[i] = dp[i-1] + pnum[i-1] + 1


print(dp[N])

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

def burger(n):
  if n == 0:
    return 'P'
  else:
    s = burger(n-1)
    return 'B' + s + 'P' + s + 'B'
  
def layer(n):
  return 2**(n+2)-3 

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

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

def search(n, x):
  global ans
  
  if x <= 0:
    pass
  elif layer(n) - n <= x:
    ans += pate(n)
  elif layhalf(n) + 1 <= x:
    ans += pate(n - 1) + 1
    search(n - 1, x - layhalf(n) - 1)
  elif layhalf(n) == x:
    ans += pate(n - 1)
  else:
    search(n - 1, x - 1)
    
search(n, x)
print(ans)

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:
        if X<=0:
            return 0
        else:
            return 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())
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):

def burger(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    if x <= 1 + B[n - 1]:
        return burger(n - 1, x - 1)
    return burger(n - 1, x - 2 - B[n - 1]) + P[n - 1] + 1


def main():
    global B, P
    N, X = tuple(map(int, input().split()))
    B, P = [1], [1]  
    for i in range(N):
        B += [B[i] * 2 + 3]
        P += [P[i] * 2 + 1]
    ans = burger(N, X)
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def burg(lev,x):
  if lev <= 0:
    return int(x>0)
  if x <= 1:
    return 0
  if 1 < x < h[lev-1]+2:
    return burg(lev-1,x-1)
  if x == h[lev-1]+2:
    return p[lev-1] + 1
  if h[lev-1]+2 < x < h[lev]:
    return p[lev-1] + 1 + burg(lev-1,x-(h[lev-1]+2))
  if x >= h[lev]:
    return p[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))

Solution (Python):
def a(n):
  return 2**(n+2)-3
def b(n):
  return 2**(n+1)-1
N,X= [int(s) for s in input().split()]
count=0
while X>0:
  if X==a(N):
    count+=b(N)
    X-=a(N)
  elif X<a(N):
    X-=1
    N-=1
  else:
    X-=a(N)+1
    count+=b(N)+1
print(count)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    
    N, X = map(int, input().split())
    
    dp = [[0,0] for i in range(N+1)]
    dp[0] = [1,1]
    for i in range(1,N+1):
        dp[i][0] = 2*dp[i-1][0] + 1
        dp[i][1] = 2*dp[i-1][1] + 3
    dp = dp[::-1]
    tmp = X
    i = 0
    j = 0
    ans = 0
    
    while tmp != 0:
        if tmp <= N - i:
            break
        if tmp < i - j + dp[i][1]:
            i += 1
        else:
            ans += dp[i][0]
            tmp -= (i - j + dp[i][1])
            if tmp >= 1:
                tmp -= 1
                ans += 1
                j = i
    print(ans)
            

main()

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

bts(n,x)
  
print(ans)

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())

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())
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))