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


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


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


def f(N, X):
    if N == 0:
        return 1 if X > 0 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 math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations

from itertools import accumulate
from bisect import bisect_left, bisect_right





def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 



N, X = l_inpl()

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 1
        else:
            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):
def thickness(l):
    return 2 ** (l + 2) - 3


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


def rec(l, x):
    if l == 0:
        return x
    t = thickness(l-1)
    if x <= 1:
        return 0
    elif x <= t + 1:
        return rec(l-1, x-1)
    elif x <= t + 2:
        return pate(l-1) + 1
    elif x <= 2 * t + 2:
        return pate(l-1) + 1 + rec(l-1, x-t-2)
    else:
        return pate(l)


def main():
    n, x = map(int, input().split())
    print(rec(n, x))


main()

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

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

print(keisan(N,X))

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

Solution (Python):
def burger(n, x):
    if x < 1:
        return 0

    
    if (n, x) == (0, 1):
        return 1

    if x <= 1 + size[n - 1]:
        return burger(n - 1, x - 1)
    else:
        return p_num[n - 1] + 1 + burger(n - 1, min(x - 2 - size[n - 1], size[n - 1]))
    


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

print(burger(n, x))

Solution (Python):
from collections import defaultdict


def burger(lv, x):
    if d[(lv, x)] >= 0:
        return d[(lv, x)]

    if x < 1 or x > cnt[lv]:
        d[(lv, x)] = 0
        return d[(lv, x)]

    
    if (lv, x) == (0, 1):
        d[(lv, x)] = 1
        return d[(lv, x)]

    half = (cnt[lv] - 1) // 2
    if x <= half:
        d[(lv, x)] = burger(lv - 1, x - 1)
        return d[(lv, x)]
    else:
        d[(lv, x)] = burger(lv - 1, half - 1) + 1 + burger(lv - 1, min(x - 1 - half, half - 1))
        return d[(lv, x)]


n, x = map(int, input().split())
cnt = [1]
for lv in range(1, 50 + 1):
    cnt.append(cnt[-1] * 2 + 3)
d = defaultdict(lambda: -1)

print(burger(n, x))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)

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

if X < N :
    print(0)
else :
    pat = [0] * (N + 1)  
    ban = [0] * (N + 1)  
    pat[0] = 1
    for i in range(1, N + 1) :
        pat[i] = 2 * pat[i - 1] + 1
        ban[i] = 2 * ban[i - 1] + 2
    def sol(level, height) :
        if height <= 0 :
            return 0
        if level == 0 :
            return 1
        if height <= 1 :
            return 0
        if height < pat[level - 1] + ban[level - 1] :
            return sol(level - 1, height - 1)
        if height == pat[level - 1] + ban[level - 1] + 1 :
            return pat[level - 1]
        if height == pat[level - 1] + ban[level - 1] + 2 :
            return pat[level - 1] + 1
        return pat[level - 1] + 1 + sol(level - 1, height - (pat[level - 1] + ban[level - 1] + 2))

    ans = sol(N, X)
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)

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

total_b = [0]
total_p = [1]
total = [1]

for i in range(N):
    b = total_b[-1]*2 + 2
    p = total_p[-1]*2 + 1
    x = b+p
    total_b.append(b)
    total_p.append(p)
    total.append(x)


def dfs(x,level):
    if x == 1 or x == 0:
        
        return 0
    if x == total[level-1] + 1:
        
        return total_p[level-1]
    if x == total[level-1] + 2:
        
        return total_p[level-1] + 1
    if x == total[level-1]*2 + 2:
        
        return total_p[level-1]*2 + 1
    if x == total[level-1]*2 + 3:
        
        return total_p[level-1]*2 + 1
    if x > 1 and total[level-1] + 1 > x:
        
        return dfs(x-1,level-1)
    if x > total[level-1] + 2 and total[level-1]*2 + 2 > x:
        
        return dfs(x - total[level-1] - 2,level-1) + total_p[level-1] + 1
ans = dfs(X,N)
print(ans)

Solution (Python):
N, X = map(int, input().split())
dp_layer = [1] * (N + 1)
dp_numP = [1] * (N + 1)

for i in range(1, N + 1):
	dp_layer[i] = 3 + 2 * dp_layer[i - 1]
	dp_numP[i] = 1 + 2 * dp_numP[i - 1]
	
x = X
countP = 0
i = N

while x > 0:
	if x >= dp_layer[i]:
		x -= dp_layer[i]
		countP += dp_numP[i]
		if x > 0:
			x -= 1
			countP += 1
	else:
		i -= 1
		x -= 1
		
print(countP)

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

hlist=[]
blist=[]
plist=[]
for i in range(N+1):
  hlist.append(2**(i+2)-3)
  
  plist.append(2**(i+1)-1)
  




num_p=0
while(True):
  
  if N==0:
    num_p+=1
    break
  elif X==1:
    break
  elif X==hlist[N]//2+1:
    num_p+=plist[N-1]+1
    break
  elif X==hlist[N]:
    num_p+=plist[N]
    break
  elif X<hlist[N]//2+1:
    X-=1
    N-=1
  else:
    num_p+=plist[N-1]+1
    X-=hlist[N]//2+1
    N-=1
  
print(num_p)

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

pb = 0
p = 0

def christmas(l, x) :
    global pb, p
    if l == 0 :
        if pb < x :
            pb += 1
            p += 1
    else :
        if pb < x :
            pb += 1
        if pb + 2**(l+1)-3 <= x :
            pb += 2**(l+1)-3
            p += 2**l-1
        elif pb < x :
            christmas(l-1, x)
        if pb < x :
            pb += 1
            p += 1
        if pb + 2**(l+1)-3 <= x :
            pb += 2**(l+1)-3
            p += 2**l-1
        elif pb < x :
            christmas(l-1, x)
        if pb < x :
            pb += 1

christmas(n, x)
print(p)

Solution (Python):
def patty_num(N):
    if N == 0:
        return 1
    return 1 + 2 * patty_num(N - 1)

def burger_height(N):
    if N == 0:
        return 1
    else:
        return 3 + 2 * burger_height(N - 1)
    
def f(N, X):
    if X == 1:
        if N == 0:
            return 1
        else:
            return 0
    elif 1 < X and X <= burger_height(N - 1) + 1:
        return f(N - 1, X - 1)
    elif X == burger_height(N - 1) + 2:
        return patty_num(N - 1) + 1
    elif burger_height(N - 1) + 2 < X and X <= 2 * burger_height(N - 1) + 2:
        return patty_num(N - 1) + 1 + f(N - 1, X - 2 - burger_height(N - 1))
    
    return 2 * patty_num(N - 1) + 1
    
N, X = map(int, input().split())
print(f(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 myfunc(L, X):
    if L==0:
        return 1 if X>0 else 0
    elif X==1:
        return 0
    elif 1<X and X<=a[L-1]+1:
        return myfunc(L-1, X-1)
    elif X==a[L-1]+2:
        return p[L-1]+1
    else:
        return p[L-1]+1+myfunc(L-1, X-a[L-1]-2)

print(myfunc(N, X))

Solution (Python):
n,x = list(map(int,input().split()))
def cal(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    ll = 2**(n+1)-3
    if x<=ll+1:
        return cal(n-1,x-1)
    if x==ll+2:
        return cal(n-1,x-2)+1
    if x<=ll+ll+2:
        return cal(n-1,ll)+1+cal(n-1,x-ll-2)
    if x==ll+ll+3:
        return 2**(n+1)-1

print(cal(n,x))

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

bur = [1]
pati = [1]
for i in range(N):
    bur.append(bur[i] * 2 + 3)
    pati.append(pati[i] * 2 + 1)


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + bur[N - 1]:
        return f(N - 1, X - 1)
    else:
        return pati[N - 1] + 1 + f(N - 1, X - 2 - bur[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())

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

layer = 1
for _ in range(N):
    layer = layer * 2 + 3

def calc(n, i, layer):
    if i == 0:
        return 0
    
    if n == 1:
        return "BPPPB"[:i].count("P")
    else:
        if i == layer // 2 + 1:
            return cntP[n-1] + 1
        elif i > layer // 2 + 1:
            return cntP[n-1] + 1 + calc(n-1, i - (layer // 2 + 1), (layer-3) // 2)
        elif i < layer // 2 + 1:
            return calc(n-1, i-1, (layer-3) // 2)

ans = calc(N, X, layer)
print(ans)

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

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

print(dp(N,X))

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

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

print(dp(N,X))

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(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 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())
def patty(L):

    p = 1
    for i in range(L):
        p = 2 * p + 1
    return (p)
def vol(L):

    m = 1
    for i in range(L):
        m  = m * 2 + 3
    return (m)
def eated(L, X):

    if L == 0:
        return 1
    m = vol(L)
    if X == 1 or X == 0:
        
        return 0
    elif X == (m + 1) / 2:
        
        
        return patty(L-1) + 1
    elif X < (m + 1) / 2:
        
        
        return eated(L-1, X-1)
    else:
        
        
        return patty(L) - eated(L, m - X)
print(eated(n, x))

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

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 f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + l[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-l[N-1])
    
print(f(N, X))

Solution (Python):
memo = [[0, 1]]

def f(n, b, p, k):
	if b+p == k: return [b, p]
	if n == 0: return [b, p+1]
	newlst1 = [b+1, p]
	if newlst1[0]+newlst1[1] == k: return newlst1
	newlst2 = [newlst1[0]+memo[n-1][0], newlst1[1]+memo[n-1][1]]
	if newlst2[0] + newlst2[1] == k: return newlst2
	if newlst2[0] + newlst2[1] > k: return f(n-1, newlst1[0], newlst1[1], k)
	newlst3 = [newlst2[0], newlst2[1]+1]
	if newlst3[0]+newlst3[1] == k: return newlst3
	newlst4 = [newlst3[0]+memo[n-1][0], newlst3[1]+memo[n-1][1]]
	if newlst4[0]+newlst4[1] == k: return newlst4
	if newlst4[0]+newlst4[1] > k: return f(n-1, newlst3[0], newlst3[1], k)
	return [newlst4[0]+1, newlst4[1]]

N, K = map(int, input().split())
for i in range(1, N):
	memo.append([2*memo[i-1][0]+2, 2*memo[i-1][1]+1])
print(f(N, 0, 0, K)[1])

Solution (Python):
n,x=map(int,input().split())
def f(n,x):
  if n==1:
    return 0 if x==1 else 1 if x==2 else 2 if x==3 else 3
  else:
    if x==1:
      return 0
    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 2**n+f(n-1,x-2**(n+1)+1)
    else:
      return 2**(n+1)-1
print(f(n,x))

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

def dp(cur,X,ans):
    if cur==0:
        if X==0:
            return ans
        else:
            return ans+1
    elif X==0:
        return ans
    elif X>0 and X<=1+L[cur-1]:
        return dp(cur-1,X-1,ans)
    elif X==2+L[cur-1]:
        return ans+P[cur-1]+1
    elif X>2+L[cur-1] and X<L[cur]:
        return dp(cur-1,X-L[cur-1]-2,ans+P[cur-1]+1)
    else:
        return ans+P[cur]
        
print(dp(N,X,0))

Solution (Python):
n, x = map(int, input().split())
pty = [[] for i in range(n + 1)]
lay = [[] for i in range(n + 1)]
pty[0] = 1
lay[0] = 1
for L in range(1, n + 1):
    pty[L] = 2 * pty[L - 1] + 1
    lay[L] = 2 * lay[L - 1 ] + 3
ans = 0
while x > 0:
    if x >= lay[L] + 1:
        x -= lay[L] + 1
        ans += pty[L] + 1
    elif x == lay[L]:
        x -= lay[L]
        ans += pty[L]
    else:
        L -= 1
        x -= 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def eat(level, X):
    if X == 0:
        return 0
    if level == 0:
        return X
    if (X-1) <= T_array[level-1]:
        return eat(level-1, X-1)
    else:
        return P_array[level-1] + 1 + eat(level-1, min(X-T_array[level-1]-2, T_array[level-1]))


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

P_array = [0] * 51
B_array = [0] * 51
T_array = [0] * 51
P_array[0] = 1
B_array[0] = 0
T_array[0] = 1

for i in range(1, 51):
    P_array[i] = P_array[i-1]*2 + 1
    B_array[i] = B_array[i-1]*2 + 2
    T_array[i] = P_array[i] + B_array[i]

print(eat(N,X))

Solution (Python):

"""
D - Christmas
https://atcoder.jp/contests/abc115/tasks/abc115_d

"""
import sys


def create_burger(n):
    if n == 0:
        return 'P'
    return 'B' + create_burger(n-1) + 'P' + create_burger(n-1) + 'B'


def solve(N, X):
    def eat_p(level, x):
        if level == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + T[level-1]:
            return eat_p(level-1, x-1)
        else:
            return P[level-1] + 1 + eat_p(level-1, x-2-T[level-1])

    T, P = [1], [1]
    for _ in range(N):
        T.append(T[-1] * 2 + 3)
        P.append(P[-1] * 2 + 1)

    return eat_p(N, X)


def main(args):
    N, X = map(int, input().split())
    ans = solve(N, X)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

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

def f(n, k):
    if k == 0:
        return 1 if n==1 else 0
    elif n == 1:
        return 0
    elif 1 < n <= 1 + a[k-1]:
        return f(n-1, k-1)
    elif n == 2 + a[k-1]:
        return 1 + p[k-1]
    elif 2 + a[k-1] < n <= 2 + 2 * a[k-1]:
        return 1 + p[k-1] + f(n-2-a[k-1], k-1)
    elif n == 3 + 2 * a[k-1]:
        return 1 + 2 * p[k-1]
    else:
        return 'Err'

ans=f(s, k)
print(ans)

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

print(ans(N,X))

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

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

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


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


print(calc(N, X))

Solution (Python):
N, X = map(int, input().split())
x = X
nums = [1]
p_count = [1]
for i in range(N):
    nums.append(2 * nums[-1] + 3)
    p_count.append(2 * p_count[-1] + 1)


def solve_p(N, X):
    if X <= 0:
        return 0
    elif N == 0:
        return 1
    else:
        if X == (nums[N]+1) // 2:
            return (p_count[N]+1) // 2
        elif X < (nums[N]+1) // 2:
            return solve_p(N - 1, X - 1)
        else:
            
            return p_count[N-1]+1+solve_p(N-1, X-(nums[N]+1)//2)


print(solve_p(N, X))
"""
burger = ["P"]
for i in range(N):
    burger.append(("B"+burger[i]+"P"+burger[i]+"B"))




print(burger[N][:x].count("P"))
"""

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 burger(L,x):
    if L == 0:
        return 0 if x == 0 else 1
    if x <= 1:
        return 0
    if x <a[L-1]+2:
        return burger(L-1,x-1)
    if x == a[L-1]+2:
        return p[L-1]+1
    if x < a[L]:
        return p[L-1]+1+burger(L-1,x-a[L-1]-2)
    if x == a[L]:
        return p[L]
print(burger(N,X))

Solution (Python):
def putty():
    N,X = map(int,input().split())
    ans = 0

    for i in range(0,N+1)[::-1]:
        width = 2**(i+2)-3
        if X <= i:   return ans
        elif X >= width - i:    return ans + 2**(i+1)-1
        else:
            mid = (width + 1) // 2
            if X == mid:    return ans + 2**(i)
            elif X < mid:   X -= 1 
            else:
                X -= 2**(i+1)-3 + 2 
                ans += 2**(i)

print(putty())

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

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

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

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


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

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

print(f(n, x))

Solution (Python):
n,x=map(int,input().split())
def b(j):
    return 2**(j+2)-3
def p(j):
    return 2**(j+1)-1
def f(n,x):
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<=b(n-1)+1:
        return f(n-1,x-1)
    elif x==b(n-1)+2:
        return p(n-1)+1
    elif 2+b(n-1)<x<=2*b(n-1)+2:
        return p(n-1)+1+f(n-1,x-b(n-1)-2)
    else:
        return 2*p(n-1)+1
print(f(n,x))

Solution (Python):
n,x=map(int,input().split())
def b(j):
    return 2**(j+2)-3
def p(j):
    return 2**(j+1)-1
def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    elif x<=b(n-1)+1:
        return f(n-1,x-1)
    elif x==b(n-1)+2:
        return p(n-1)+1
    elif 2+b(n-1)<x<=2*b(n-1)+2:
        return p(n-1)+1+f(n-1,x-b(n-1)-2)
    else:
        return 2*p(n-1)+1
print(f(n,x))

Solution (Python):
N, X = map(int, input().split())
b, p = [1], [1]

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

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

L = [0] * (N + 1)
P = [0] * (N + 1)
for i in range(N+1):
    L[i] = 2 ** (i + 2) - 3
    P[i] = 2 ** (i + 1) - 1

def rec(N, X):    

    if X <= 0:
        return(0)
        
    if N == 0:
        return(1)
    
    if X < L[N - 1] + 2:
        return(rec(N - 1, X - 1))
        
    if X == L[N - 1] + 2:
        return(P[N - 1] + 1)
    
    if X > L[N - 1] + 2:
        return(P[N - 1] + 1 + rec(N - 1, X - L[N - 1] - 2))


print(rec(N, X))

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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 < (2 + a[N-1]):
            return _f(N-1, X-1)
        elif X == (2 + a[N-1]):
            return 1 + p[N-1]
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _f(N, X)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    X = int(next(tokens))  
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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)
        elif X == (2 + a[N-1]):
            return 1 + p[N-1]
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _f(N, X)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    X = int(next(tokens))  
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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)
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _f(N, X)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    X = int(next(tokens))  
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Solution (Python):
p=lambda n:2**(n+1)-1
a=lambda n:2**(n+2)-3
def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x>1+a(n-1):
        return p(n-1)+1+f(n-1,x-2-a(n-1))
    return f(n-1,x-1)
n,x=map(int,input().split())
print(f(n,x))

Solution (Python):
p=lambda n:2**(n+1)-1
a=lambda n:2**(n+2)-3
def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x<=1+a(n-1):
        return f(n-1,x-1)
    return p(n-1)+1+f(n-1,x-2-a(n-1))
n,x=map(int,input().split())
print(f(n,x))

Solution (Python):
p = lambda n:2**(n+1)-1
a = lambda n:2**(n+2)-3


def dfs(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x<=1+a(n-1):
        return dfs(n-1,x-1)
    else:
        return p(n-1)+1 + dfs(n-1,x-2-a(n-1))

n, x = map(int, input().split())
print(dfs(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
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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


def rec(n: int, x: int, a: list, p: list) -> int:
    if x <= 0:
        raise ValueError

    elif n == 0:
        return 1

    elif x == 1:
        return 0

    elif 1 < x < a[n-1] + 2:
        return rec(n-1, x-1, a, p)

    elif x == a[n-1] + 2:
        return p[n-1] + 1

    elif a[n-1] + 2 < x < 2*a[n-1] + 3:
        return p[n-1] + 1 + rec(n-1, x - a[n-1] - 2, a, p)

    elif x == 2*a[n-1] + 3:
        return 2 * p[n-1] + 1

n,x = li()
a = [1]
p = [1]

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

print(rec(n, x, a, p))

Solution (Python):

"""
Created on Sun May 19 16:57:17 2019

@author: Yamazaki Kenichi
"""

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

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

ans = 0
for i in range(2,N+2):
    if X - (dp[-i][1] + 2) >= 0:
        ans += dp[-i][0] + 1
        X -= (dp[-i][1] + 2)

    else:
        X -= 1

    if i == N+1 and X >= 1:
        ans += 1

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

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

print(f(n,x))

Solution (Python):
def bread_cnt(lev):
  return 2**(lev+1) - 2

def patty_cnt(lev):
  return 2**(lev+1) - 1

def burger_cnt(lev):
  return 2**(lev+2) - 3

def solve(n, x):
  return _solve(n, x, 0)
  
def _solve(n, x, p):
  total_s = burger_cnt(n)
  mid = (total_s+1)//2
  
  if x==1:
    return p + (1 if n==0 else 0)
  elif 1 < x and x <= mid:
    reach_mid = 1 if x==mid else 0
    return _solve(n-1, x-1-reach_mid, p+reach_mid)
  elif mid < x and x < total_s:
    return _solve(n-1, x-2-burger_cnt(n-1), p+1+patty_cnt(n-1))
  elif x == total_s:
    return p+patty_cnt(n)

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

Solution (Python):
N,K = map(int,input().split())
import sys
sys.setrecursionlimit(10000000)

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

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:
    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):
memo = [-1]*100
mepp = [-1]*100
def getPB(N,k):
    if (N==0):
        return 1,1 if k>0 else 0
    if (memo[N] != -1 and k >= memo[N] and mepp[N]!=-1 ):
        return memo[N] , mepp[N]
    if (memo[N] != -1 and k <= 0):
        return memo[N] , 0
    
    c,p = 1,0
    _c,_p=getPB(N-1,k-c)
    c,p=c+_c,p+_p
    c,p=c+1,(p+1 if (k-c>0) else p)
    _c,_p=getPB(N-1,k-c)
    c,p=c+_c,p+_p
    c += 1
    memo[N] = c
    if (k-c>=0):
        mepp[N] = p
    return c,p
N,X = [ int(it) for it in input().split() ]
print ( getPB(N,X)[1] )