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):
import sys
from math import *
from fractions import gcd
readints=lambda:map(int, input().strip('\n').split())

calc=[0]*55
calc[0]=1
for i in range(1,52):
    calc[i] = 3 + 2*calc[i-1]


n,x=readints()
x-=1 


cache={}

def solve(L, i):
    if i<0:
        return 0
    if L==0:
        return 1
    else:
        if (L,i) in cache:
            return cache[(L,i)]
        m = calc[L] // 2
        res = 0
        if i>=m:
            res += solve(L-1,calc[L-1]-1) + 1
            res += solve(L-1,i-m-1)
            cache[(L,i)]=res
        else:
            cache[(L,i)]=solve(L-1, i-1)
        return cache[(L,i)]
        


print(solve(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)]

ans = 0

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


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

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

burger = [[1,1]]

for i in range(n):
    burger.append([burger[-1][0]*2+3,burger[-1][1]*2+1])


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


print(eat(n,x))

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

b = [[1,1]]

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

ans = 0
for i in range(len(b)):
    if x >= b[-1-i][0]:
        x -= b[-1-i][0]
        ans += b[-1-i][1]
        if x > 0:
            x-=1
            ans += 1
        if x>=b[-1-i][0]:
            x -= b[-1 - i][0]
            ans += b[-1 - i][1]
            break
    x-=1
    if x<=0:
        break

print(ans)

Solution (Python):

def count(N):
    pn = 2**(N+1)-1 
    bn = 2**(N+1)-2 
    rn = pn + bn    
    return pn, bn, rn
    
if __name__ == "__main__":
    N, X = map(int, input().split())
    pn,bn,rn = count(N)
    mid = (1+rn)//2
    cnt = 0
    
    while N > 0:
        
        
        pn_prev, bn_prev, rn_prev = count(N-1)

        if X == 1:
            break
        elif X == mid:
            cnt +=  pn_prev + 1
            break
        elif rn == X:
            cnt += 2*pn_prev + 1
            break
        elif 1 < X < mid:
            X -= 1
        elif mid < X < rn:
            cnt += pn_prev + 1
            X -= mid

        pn, bn, rn = pn_prev,bn_prev,rn_prev
        mid = (1+rn)//2
        N -= 1
        if N == 0:
            cnt += 1
    print(cnt)

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

Solution (Python):
N, X = [int(a) for a in input().split(" ")]
numt = [1]*51
nump = [0]*51
for i in range(1,51):
    numt[i]=2*numt[i-1]+3
    nump[i]=2*nump[i-1]+1

def rec(n, i):
    if n==0:
        return 1
    if i==0:
        return 0
    elif i==numt[n]-1:
        return 2*nump[n]+1
    mid = numt[n]//2
    if i==mid:
        return 1+nump[n]
    elif i>mid:
        return rec(n-1, i-mid-1)+nump[n]+1
    else:
        return rec(n-1, i-1)
    
print(rec(N, X-1))

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)
    return 2 ** n + main(n - 1, x - (2 ** (n + 1) - 1))


print(main(n, x))

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

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

ans = 0
for n in range(N,-1,-1):
  if X > (2**(n+2) - 3) / 2 :
    ans += 2**n 
    X = X - (2**(n+1) - 3) - 2
  else:
    X -= 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 <= 1+a[N-1]:
        return dfs(N-1,X-1)
    else:
        return p[N-1]+1+dfs(N-1,X-2-a[N-1])

print(dfs(N,X))

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

max_layer = 50
all_layer = [0]*(max_layer+1)
pate = [0]*(max_layer+1)
all_layer[0] = 1
pate[0] = 1

for i in range(1,max_layer+1):
    all_layer[i] = 2*all_layer[i-1] + 3
    pate[i] = 2*pate[i-1] + 1

def dfs(level, remain):
    ans = 0
    if level == 0:
        return 1

    if remain > 0:
        remain -= 1
    if remain > 0:
        if all_layer[level-1] <= remain:
            remain -= all_layer[level-1]
            ans += pate[level-1]
        else:
            ans += dfs(level-1, remain)
            return ans
    if remain > 0:
        remain -= 1
        ans += 1
    if remain > 0:
        if all_layer[level-1] <= remain:
            remain -= all_layer[level-1]
            ans += pate[level-1]
        else:
            ans += dfs(level-1, remain)
            return ans
    return ans
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):
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:
        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 f(n):
    
    if n == 0:
        return 1
    else:
        return 2 * f(n - 1) + 3


def g(n):
    
    if n == 0:
        return 1
    else:
        return 2 * g(n - 1) + 1


def dfs(n, x):
    
    m = f(n)
    
    a = (m + 1) // 2

    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x < a:
        return dfs(n - 1, x - 1)
    elif x == a:
        return g(n - 1) + 1
    elif x >= a:
        return g(n - 1) + 1 + dfs(n - 1, x - a)
    elif x == m:
        return 2 * g(n - 1) + 1


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

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


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


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

    elif 1 < x <= H[n - 1] + 1:
        return dfs(n - 1, x - 1)

    elif x == H[n - 1] + 2:
        return P[n - 1] + 1

    elif H[n - 1] + 2 < x <= 2 * H[n - 1] + 2:
        return P[n - 1] + 1 + dfs(n - 1, x - H[n - 1] - 2)

    elif x == 2 * H[n - 1] + 3:
        return 2 * P[n - 1] + 1


print(dfs(N, X))

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


def length(n):
    return 4*2**n - 3


def func(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    half = length(n) // 2
    if x <= half:
        return func(n - 1, x - 1)
    elif x == half + 1:
        return func(n - 1, x - 1) + 1
    else:
        return (2*2**(n-1) - 1) + 1 + func(n - 1, x - length(n-1) - 2)


print(func(N, X))

Solution (Python):
N,X=map(int,input().split())
dp={}
def f(n,x):
    if (n,x) in dp:
        return dp[(n,x)]
    elif (n,x)==(0,1):
        return 1
    else:
        if x==1:
            answer=0
            return answer
        elif 2<=x<=2**(n+1)-2:
            answer=f(n-1,x-1)
            return answer
        elif x==2**(n+1)-1:
            answer=f(n-1,2**(n+1)-3)+1
            return answer
        elif 2**(n+1)<=x<=2**(n+2)-4:
            answer=f(n-1,2**(n+1)-3)+f(n-1,x-2**(n+1)+1)+1
            return answer
        else:
            answer=2*f(n-1,2**(n+1)-3)+1
            return answer
print(f(N,X))

Solution (Python):
N,X=map(int,input().split())
dp={}
def f(n,x):
    if (n,x) in dp:
        return dp[(n,x)]
    elif (n,x)==(0,1):
        return 1
    else:
        if x==1:
            answer=0
            dp[(n,x)]=answer
            return answer
        elif 2<=x<=2**(n+1)-2:
            answer=f(n-1,x-1)
            dp[(n,x)]=answer
            return answer
        elif x==2**(n+1)-1:
            answer=f(n-1,2**(n+1)-3)+1
            dp[(n,x)]=answer
            return answer
        elif 2**(n+1)<=x<=2**(n+2)-4:
            answer=f(n-1,2**(n+1)-3)+f(n-1,x-2**(n+1)+1)+1
            dp[(n,x)]=answer
            return answer
        else:
            answer=2*f(n-1,2**(n+1)-3)+1
            dp[(n,x)]=answer
            return answer
print(f(N,X))

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

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

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


def eat(neat,level):

    if level == 0:
        return 1 if neat > 0 else 0

    elif neat < 2:
        return 0

    t = thickness[level]
    center = t//2 + 1

    if neat == t:
        return B(level)

    elif neat < center:
        return eat(neat-1, level-1)

    else: 
        return 1 + B(level-1) + eat(neat - center, level-1)

print(eat(X, N))

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

def eat(l,x):
    if x==0:
        return 0
    if l==0:
        return 1
    if x<b[l-1]+2:
        ans=eat(l-1,x-1)
    else:
        ans=p[l-1]+1+eat(l-1,x-2-b[l-1])
    return ans
print(eat(n,x))

Solution (Python):
N,X = map(int, input().split())
num, p = [1], [1]
index = 1
while N >= index:
    num.append(2*num[-1] + 3)
    p.append(2*p[-1] + 1)
    index +=1

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

print(ans(N, X))

Solution (Python):
import sys

input = sys.stdin.readline
N, X = list(map(int, input().split()))


def p_num(l):
    """レベルlバーガーに含まれるパティの数を返す
    """
    return 2**(l+1)-1


def l_num(l):
    """レベルlバーガーに含まれる層の数
    """
    return 2**(l+2)-3


def p_num_l(level, x):
    """レベルlevelバーガーの1, 2, ...x層までのうちのパティーの数を返す
    """
    if level == 0:
        return 1
    if x == 1:
        return 0
    elif x == 2**(level+1)-1:
        return p_num(level-1)+1
    elif x == 2**(level**2)-3:
        return 2*p_num(level-1)+1
    elif x < 2**(level+1)-1:
        return p_num_l(level-1, x-1)
    else:
        return p_num(level-1)+1+p_num_l(level-1, x-2-l_num(level-1))


print(p_num_l(N, X))

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

def get_size(level):
    return (1 << (level+2)) - 3

def get_patty(level):
    return (1 << (level+1)) - 1

ans = 0
while X > 0:
    if get_size(N) > X:
        X -= 1
        N -= 1
    else:
        X -= get_size(N)
        ans += get_patty(N)
        if X > 0:
            ans += 1
            X -= 1
print(ans)

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

layer_size = [1]
P_cnt = [1]

for _ in range(50):
    layer_size.append(layer_size[-1]*2+3)
    P_cnt.append(P_cnt[-1]*2+1)
    
def solve(level,x):
    if x == 1:
        return 0 if level > 0 else 1
    l = layer_size[level-1]
    p = P_cnt[level-1]
    if x <= 1+l:
        return solve(level-1,x-1)
    elif x == l+2:
        return p+1
    elif x <= 2*l+2:
        return p+1+solve(level-1,x-l-2)
    else:
        return 2*p+1

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

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

n_sum= X
answer = [0]
def saiki(layer,n_sum,sum_p):
    
    
    
    
    if n_sum == 0:
        answer[0] = sum_p
        return 
    if layer == 1:
        if n_sum == 1:
            answer[0] = sum_p
        elif n_sum == 2:
            answer[0] = sum_p+1
        elif n_sum ==3:
            answer[0] = sum_p+2
        else:
            answer[0] = sum_p+3
        return

    
    layer_sum = 2**(layer+2)-3
    
    pre_layer_sum = 2**(layer+1)-3
    pre_p_sum = 2**(layer)-1
    
    if n_sum  < layer_sum //2 +1 :
        
        n_sum -= 1
        saiki(layer-1,n_sum,sum_p)
    
    else:
        
        n_sum -= (pre_layer_sum+2)
        sum_p += (1+pre_p_sum)
        saiki(layer-1,n_sum,sum_p)

saiki(N,X,0)

print(answer[0])

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

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x == 1:
        return 0
    elif x <= 1 + thickness[n-1]:
        return f(n-1, x-1)
    elif x == 2 + thickness[n-1]:
        return patties[n-1] + 1
    elif x <= 2 + 2*thickness[n-1]:
        return patties[n-1] + 1 + f(n-1, x-(2 + thickness[n-1]))
    else:
        return 2*patties[n-1] + 1
    
print(f(N, X))

Solution (Python):
def _level(n):
	if n == 0:
		return 1
	else:
		return 3 + 2 * level(n-1)

def _eat(n, x):
	if n == 0:
		return 1 if x > 0 else 0
	if x <= 1:
		return 0
	if x <= 1 + level(n-1):
		return eat(n-1, x-1)
	if x == 1 + level(n-1) + 1:
		return eat(n-1, level(n-1)) + 1
	if x <= 1 + level(n-1) + 1 + level(n-1):
		return eat(n-1, level(n-1)) + 1 + eat(n-1, x - (1 + level(n-1) + 1))
	else:
		return eat(n-1, level(n-1)) + 1 + eat(n-1, level(n-1))

store = {}

def level(n):
	if n not in store:
		store[n] = _level(n)
	return store[n]

def eat(n, x):
	if (n, x) not in store:
		store[(n, x)] = _eat(n, x)
	return store[(n, x)]


print(eat(*map(int, input().split())))

Solution (Python):
def patty(n,x):
    if x == 0:
        return 0
    elif n == 0:
        
        return 1
    elif x == 1 and n > 0:
        return 0
    num = 2 ** (n+2) - 3
    pre_num = 2 ** (n+1) - 3
    if x == num:
        
        return 2 * patty(n-1,pre_num) + 1
    elif x > pre_num + 1:
        
        return patty(n-1,pre_num) + 1 + patty(n-1,x - pre_num - 2)
    elif x == pre_num + 1:
        
        return patty(n-1,pre_num)
    else:
        
        return patty(n-1,x-1)

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

print(patty(n,x))

Solution (Python):
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

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


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

print(f(N, X))

Solution (Python):
def solve(string):
    n, x = map(int, string.split(" "))
    t = ["P"]
    for _ in range(10):
        t.append("B{}P{}B".format(t[-1], t[-1]))
    l, p = [1], [1]
    for _ in range(n):
        l.append(2 * l[-1] + 3)
        p.append(2 * p[-1] + 1)

    def rec(i, x):
        if i <= 10:
            return t[i][:x].count("P")
        if x > l[i - 1] + 2:
            return p[i - 1] + 1 + rec(i - 1, x - l[i - 1] - 2)
        elif x == l[i - 1] + 2:
            return p[i - 1] + 1
        else:
            return rec(i - 1, x - 1)

    return str(rec(n, x))


if __name__ == '__main__':
    print(solve(input()))

Solution (Python):
N,X=map(int,input().split())
def an(n):
    return 2**(n+1)-1
def bn(n):
    return 2**(n+2)-3
ans=0
while(N+1):
    if X==0:

        print(ans)
        quit()
    if X==bn(N):
        ans+=an(N)
        print(ans)
        quit()
    if X<=(bn(N)-1)/2:
        X-=1
        N-=1
    elif X==(bn(N)-1)/2+1:
        ans+=an(N-1)+1
        print(ans)
        quit()
    else:
        X=X-(bn(N-1)+2)
        ans+=an(N-1)+1
        N-=1
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return POW(x, y // 2) ** 2 % MOD
    else:
        return POW(x, y // 2) ** 2 * x % MOD
def mod_factorial(x, y): return x * POW(y, MOD - 2) % MOD
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter

patis = [INF] * 51
layers = [INF] * 51
patis[0] = layers[0] = 1

def calc_layers(n):
    if layers[n] == INF:
        layers[n] = 3 + calc_layers(n - 1) * 2
    return layers[n]
calc_layers(50)

def calc_patis(n):
    if patis[n] == INF:
        patis[n] = 1 + calc_patis(n - 1) * 2
    return patis[n]
calc_patis(50)

def dfs(n, x):
    if layers[n] <= x:
        return patis[n], x - layers[n]
    ret = 0
    x -= 1
    if x <= 0:
        return ret, 0
    r, x = dfs(n - 1, x)
    ret += r
    if x <= 0:
        return ret, 0
    x -= 1
    ret += 1
    if x <= 0:
        return ret, 0
    r, x = dfs(n - 1, x)
    ret += r
    if x <= 0:
        return ret, 0
    x -= 1
    ret += 1
    return ret, x

def main():
    N, X = LI()
    ans, _ = dfs(N, X)
    return ans

print(main())

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

l1 = 'BPPPB'

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

dp = [-1]*51

def solve(n, x):
    if n == 0:
        return 1
    l_num = L[n]
    temp = 0
    if dp[n-1]==-1:
        temp = solve(n-1, L[n-1])
        dp[n-1] = temp
    else:
        temp = dp[n-1]

    if x == l_num//2+1:
        return temp+1
    elif n < x < l_num//2+1:
        return solve(n-1, x-1)
    elif x > l_num//2+1:
        
        
        return temp+1 +\
                solve(n-1, x-l_num//2-1)
    elif x <= n:
        return 0

print(solve(N,X))

Solution (Python):
import sys

nx = input().split()
n = int(nx[0])
x = int(nx[1])
count = 0


lenlist = []
for i in range(n + 1):
    if i == 0:
        lenlist.append(1)
    else:
        lenlist.append(lenlist[-1] * 2 + 3)

pcountlist = []
for i in range(n + 1):
    if i == 0:
        pcountlist.append(1)
    else:
        pcountlist.append(pcountlist[-1] * 2 + 1)


def incr_count(nn, xx):
    global count

    if nn == 0:
        if xx > 0:
            count += 1
        return

    if xx <= 1:
        pass
    if 1 < xx and xx <= lenlist[nn] // 2:
        incr_count(nn - 1, xx - 1)
    if lenlist[nn] // 2 < xx:
        count += pcountlist[nn - 1]
        count += 1
        incr_count(nn - 1, xx - lenlist[nn] // 2 - 1)


incr_count(n, x)
print(count)

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


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

print(calc(N, X))

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

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

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

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

height=[-1]*51
niku=[-1]*51
height[0]=1
niku[0]=1

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

def rec(l, x):
    if x==1:
        if l==0:
            return 1
        else:
            return 0
    
    if x < 1+height[l-1]+1:
        return rec(l-1, x-1)
    elif x == 1+height[l-1]+1:
        return 1 + niku[l-1]
    elif x <= height[l] - 1:
        return niku[l-1] + 1 + rec(l-1, x-height[l-1]-2)
    else:
        return 2*niku[l-1]+1
print(rec(N, X))

Solution (Python):

ans = 0
def count_ans(level, index, len_dic, p_dic):
    global ans
    if level == 0:
        ans += 1
    else:
        if index == 0:
            pass
        elif index == len_dic[level] // 2:
            ans += 1
            ans += p_dic[level - 1]
        elif index == len_dic[level] - 1:
            ans += p_dic[level]
        elif index > len_dic[level] // 2:
            ans += p_dic[level - 1] + 1
            index_next = index - len_dic[level - 1] - 2
            count_ans(level - 1, index_next, len_dic, p_dic)
        else:
            index_next = index - 1
            count_ans(level - 1, index_next, len_dic, p_dic)


def get_len_dic(level):
    len_dic = [1]
    for i in range(level):
        len_dic.append(len_dic[-1] * 2 + 3)
    return len_dic

def get_p_dic(level):
    p_dic = [1]
    for i in range(level):
        p_dic.append(p_dic[-1] * 2 + 1)
    return p_dic

def main():
    global ans
    level, eat_num = map(int, input().split())
    len_dic = get_len_dic(level)
    p_dic = get_p_dic(level)
    count_ans(level, eat_num - 1, len_dic, p_dic)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache

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


@lru_cache(maxsize=None)
def count_patti(level, index):
    """
    左から index 番目までのパティの数
    :param level:
    :param index:
    :return:
    """
    if level == 0:
        return 1
    if index == 0:
        return 0
    if 1 <= index < (sizes[level] - 1) / 2:
        return count_patti(level - 1, index - 1)
    if index == (sizes[level] - 1) / 2:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1
    if (sizes[level] - 1) / 2 < index < sizes[level] - 1:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1 + \
               count_patti(level - 1, index - (sizes[level] - 1) / 2 - 1)
    else:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1 + \
               count_patti(level - 1, sizes[level - 1] - 1)


print(count_patti(n, x - 1))

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7
dy = [0,1,0,-1]
dx = [1,0,-1,0]
ddy = [0,1,1,1,0,-1,-1,-1]
ddx = [1,1,0,-1,-1,-1,0,1]

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

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

import sys

def ln(n: int):
    return pow(2,n+1) - 3

def pn(n: int):
    return pow(2,n) - 1

def calc(N: int, X: int):
    if N == 0:
        return 0
    if N == 1:
        return 1
    n1 = ln(N - 1)
    if X == 1:
        return 0
    elif X <= 1 + n1:
        return calc(N-1,X-1)
    elif X == 2 + n1:
        return 1 + calc(N-1,X-1)
    elif X <= 2 + 2*n1:
        return 1 + pn(N-1) + calc(N-1,X-2-n1)
    else:
        return 1 + pn(N-1)*2

def solve(N: int, X: int):
    print(calc(N + 1,X))
    return



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))  
    solve(N, X)

if __name__ == '__main__':
    main()

Solution (Python):

import sys
import functools
INF = float("inf")


@functools.lru_cache(None)
def hight(n):
    if n == 0:
        return 1
    else:
        return 2*hight(n-1)+3


@functools.lru_cache(None)
def paty(n):
    if n == 0:
        return 1
    else:
        return 2*paty(n-1)+1


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

    if x == 0:
        return 0
    elif x == 1:
        return 0
    elif x < hight(n-1)+2:
        return rec(n-1, x-1)
    elif x == hight(n-1)+2:
        return paty(n-1) + 1
    else:
        
        return paty(n-1)+1 + rec(n-1, x-(hight(n-1)+2))


def solve(N: int, X: int):
    print(rec(N, X))

    return


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))  
    solve(N, X)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import functools
INF = float("inf")


@functools.lru_cache(None)
def hight(n):
    return 2**(n+2)-3


@functools.lru_cache(None)
def paty(n):
    return 2**(n+1)-1


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

    if x == 0:
        return 0
    elif x == 1:
        return 0
    elif x < hight(n-1)+2:
        return rec(n-1, x-1)
    elif x == hight(n-1)+2:
        return paty(n-1) + 1
    else:
        
        return paty(n-1)+1 + rec(n-1, x-(hight(n-1)+2))


def solve(N: int, X: int):
    print(rec(N, X))

    return


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))  
    solve(N, X)


if __name__ == '__main__':
    main()

Solution (Python):

burger = [1 for i in range(52)]
for i in range(1,52):
    burger[i] = burger[i-1]*2+3
patty = [1 for i in range(52)]
for i in range(1,52):
    patty[i] = patty[i-1]*2 + 1
def solve(L,X):
    if X == 0:
        return 0
    if burger[L] == X:
        return patty[L]
    elif (burger[L]-1)//2 + 1 == X:
        return patty[L-1] + 1
    elif (burger[L]-1)//2 + 1 > X:
        return solve(L-1,X-1)
    elif (burger[L]-1)//2 + 1 < X:
        return patty[L-1] + 1 + solve(L-1,X-burger[L-1]-2)

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

Solution (Python):
N, X = map(int, input().split())
def bisearch(n, l):
    half = (2**(n+2)-3) // 2
    return 0 if l <= 0 else 2**n + bisearch(n-1, min(l - 1 - half, half)) if half < l else bisearch(n-1, l-1)
print(bisearch(N, X))

Solution (Python):
N, X = map(int, input().split())
def bisearch(n, l):
    if l <= 0:
        return 0
    half = (2**(n+2)-3) // 2
    if half < l:
        return 2**(n) + bisearch(n-1, min(l - 1 - half, half))
    else:
        return bisearch(n-1, l-1)

print(bisearch(N, X))

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

layers={0:1}
def layers_of_level(n):
    if n in layers:
        return layers[n]
    layers[n] = 2*layers_of_level(n-1)+3
    return layers[n]

def how_many_putty(n,x):
    if n==0 and x==1:
        return 1
    if n==layers_of_level(n):
        return 2**(n+1)-1

    total_layers = layers_of_level(n)
    if x==1:
        return 0
    if x <= 1+layers_of_level(n-1):
        return how_many_putty(n-1, x-1)
    if x == 1+layers_of_level(n-1)+1:
        return how_many_putty(n-1, x-2)+1
    if x <= 1+2*layers_of_level(n-1)+1:
        return how_many_putty(n-1,layers_of_level(n-1))+1+ how_many_putty(n-1,x-layers_of_level(n-1)-2)
    else:
        return 2*how_many_putty(n-1,layers_of_level(n-1))+1

print(how_many_putty(N,X))

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

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

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

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

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 p[N-1]+1+f(N-1, X-2-b[N-1])

print(f(N, X))

Solution (Python):


def io_generator():
	return input()



def n_pat(a_n):
	return 2**a_n - 1
	
def n_size(a_n):
	return 4 * (2** (a_n -1))- 3
	
def get_size(n,x):
	if x == 0:
		return 0
	elif x==1:
		return 0
	elif x < 1 + n_size(n):
		return get_size(n-1, x -1)
	elif x == 1 + n_size(n):
		return n_pat(n)
	elif x == 1 + n_size(n) + 1:
		return n_pat(n) + 1
	elif x < 1 + n_size(n) +1 + n_size(n):
		offset=2 + n_size(n)
		return n_pat(n)+1+get_size(n-1, x - offset)
	else:
		return n_pat(n)+1+n_pat(n)

def main(io):
	n,x= map(int, io().split())
	return get_size(n,x)
	
	
	



if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))