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

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

        if x < 2:
            return 0

        if a[n] - 1 <= x:
            return p[n]

        if 1 + a[n] // 2 < x:
            return p[n - 1] + 1 + solve(n - 1, x - (a[n] // 2 + 1))
        elif 1 + a[n] // 2 == x:
            return p[n - 1] + 1
        else:
            return solve(n - 1, x - 1)

    print(solve(n, x))


if __name__ == '__main__':
    resolve()

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

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

def f(n):
	if n == 0:
		return 1
	return 2 * f(n-1) + 3

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

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

num = f(n)

ans = 0
while True:
	if num < 10 ** 5:
		break
	tmp = num // 2 + 1

	if x > tmp:
		ans += p(n) // 2 + 1
		x -= tmp
		num -= tmp + 1
	elif x < tmp:
		num -= tmp + 1
		x -= 1
	else:
		print(p(n-1)+1)
		sys.exit()
	n -= 1

string = f2(n)
if len(string) <= x:
	print(p(n)+ans)
else:
	for i in range(x):
		if string[i] == 'P':
			ans += 1
	print(ans)

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

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




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


ans = f(n, x)
print(ans)

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

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




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


ans = f(n, x)
print(ans)

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

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

Solution (Python):
N, X = map(int, input().split())
table = [None] * (N + 1)
table[0] = (1, 1)


def check_X(x, p):
    if x >= X:
        print(p)
        exit()


def dfs(n, x, p):
    check_X(x, p)
    if table[n] is None or x + table[n][0] > X:
        
        new_x, new_p = x + 1, p

        
        new_x, new_p = dfs(n - 1, new_x, new_p)
        check_X(new_x, new_p)

        
        new_x += 1
        new_p += 1

        
        new_x, new_p = dfs(n - 1, new_x, new_p)

        
        new_x += 1
        check_X(new_x, new_p)

        table[n] = (new_x - x, new_p - p)
        return new_x, new_p
    else:
        dx, dp = table[n]
        return x + dx, p + dp


dfs(N, 0, 0)

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

def F(N, X):
  if N == 0:
    if X > 0:
      return 1
    else:
      return 0

  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 b[N-1] + 1

  if a[N-1] + 2 < X <= 2*a[N-1] + 2:
    return b[N-1] + 1 + F(N-1, X - 2 - a[N-1])

  if X == 2 * a[N-1] + 3:
    return 2 * b[N-1] + 1

print(F(N, X))

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

N, X = map(int, readline().rstrip().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])

def main():
    print(f(N, X))

if __name__ == '__main__':
    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 x==0:
        return 0
    elif x==1:
        if n==0:
            return 1
        else:
            return 0

    elif 1<x<=(1+a[n-1]):
        return f(n-1,x-1)

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

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

    else:
        return 2*p[n-1]+1

print(f(n,x))

Solution (Python):

import sys


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

    
    
    def f(N: int, X: int):
        aN = 2 ** (N + 2) - 3
        bN = 2 ** (N + 1) - 1
        if X >= aN:
            return bN

        aN1 = 2 ** ((N - 1) + 2) - 3

        ans = 0

        X -= 1
        if X <= 0:
            return ans

        ans += f(N - 1, X)
        X -= aN1
        if X <= 0:
            return ans

        ans += 1
        X -= 1
        if X <= 0:
            return ans

        ans += f(N - 1, X)
        X -= aN1
        if X <= 0:
            return ans

        X -= 1
        if X <= 0:
            return ans

        assert False

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


if __name__ == '__main__':
    main()

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

Solution (Python):
n,x=map(int,input().split())
def func(n,x):
  if n==1:
    return 'BPPPB'[:min(x,5)].count('P')
  else:
    ret=0
    a=2**n+3*(2**n-1)
    if x>=a-n:
      return 2**(n+1)-1
    elif x>a//2:
      return func(n-1,x)+1+func(n-1,x-a//2-1)
    else:
      return func(n-1,x-1)
print(func(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 1
        else:
            return 0
    elif X==1:
        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 2+a[N-1]<X<=2+2*a[N-1]:
        return p[N-1]+1+f(N-1,X-2-a[N-1])
    else:
        return 2*p[N-1]+1

print(f(N,X))

Solution (Python):


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

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

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

def solver(n, x):
    a = get_a(n)
    p = get_p(n)
    if x >= a:
        ans = p
    elif x == 0:
        ans = 0
    elif 1 <= x < (1 + a) // 2:
        ans = solver(n - 1, x - 1)
    elif x == (1 + a) // 2:
        ans = get_p(n - 1) + 1
    elif (1 + a) // 2 < x < a:
        ans = solver(n - 1, x - get_a(n - 1) - 2) + get_p(n - 1) + 1

    return ans

def main():
    print(solver(N, X))

if __name__ == "__main__":
    main()

Solution (Python):
def DFS(N,X):
    if N==0:return 1
    elif X==1:return 0
    elif 1<X<=1+B[N-1]:return DFS(N-1,X-1)
    elif X==2+B[N-1]:return P[N-1]+1
    elif 2+B[N-1]<X<=2+2*B[N-1]:return P[N-1]+1+DFS(N-1,X-2-B[N-1])
    elif X==2*B[N-1]+3:return 2*P[N-1]+1


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

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

print(DFS(n,x))

Solution (Python):
def DFS(N,X):
    if N==0:return 0 if X<=0 else 1
    elif X<=1+B[N-1]:
        return DFS(N-1,X-1)
    else:
        return P[N-1]+1+DFS(N-1,X-2-B[N-1])


n,x=map(int,input().split())
B,P=[1],[1]

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

print(DFS(n,x))

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


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


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, X = map(int, input().split())
    B = 1
    P = 1
    for i in range(N):
        B = 2 * B + 3
        P = 2 * P + 1

    def cnt(X, B, P, ans):
        if B == 5:
            if X == 5:
                return ans + 3
            elif X == 4:
                return ans + 3
            elif X == 3:
                return ans + 2
            elif X == 2:
                return ans + 1
            else:
                return ans
        if X == B:
            return ans + P
        elif X > B // 2 + 1:
            ans += P // 2 + 1
            P = P // 2
            X = X - (B // 2 + 1)
            B = B // 2 - 1
            return cnt(X, B, P, ans)
        elif X == B // 2 + 1:
            ans += P // 2 + 1
            return ans
        else:
            B = B // 2 - 1
            P = P // 2
            X -= 1
            return cnt(X, B, P, ans)

    answer = cnt(X, B, P, 0)
    print(answer)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]





N, X = mi()

def rec(level, pos, score):
    
    if level == 0:
        return score + 1
    half = 2**(level+1) - 2
    if pos == 0:
        return score
    elif pos == half * 2:
        return score + 2**(level+1) - 1
    elif pos == half:
        return score + 2**(level)
    elif pos > half:
        score += 2**(level)
        pos -= half + 1
    else:
        pos -= 1
    return rec(level-1, pos, score)
    
X -= 1
print(rec(N, X, 0))

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]





N, X = mi()
'''
def rec(level):
    if level == 0:
        return 'P'
    return 'B' + rec(level-1) + 'P' + rec(level-1) + 'B'

b = rec(N)
print(b)
'''
X -= 1
cnt = 0
level = N
while True:
    if level == 0:
        cnt += 1
        break
    half = 2**(level+1) - 2
    
    if X == 0:
        break
    elif X == half * 2:
        cnt += 2**(level+1) - 1
        break
    elif X > half:
        cnt += 2**(level)
        X -= half + 1
    elif X == half:
        cnt += 2**(level)
        break 
    else:
        X -= 1
    level -= 1
print(cnt)

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


def f(P, S, L, X, count):
    if L == 0:
        return count + P[0]

    if X == 1:
        return count
    elif X <= 1 + S[L-1]:
        return f(P, S, L-1, X-1, count)
    elif X == 1 + S[L-1] + 1:
        return count + P[L-1] + 1
    elif X <= 1 + S[L-1] + 1 + S[L-1]:
        return f(P, S, L-1, X-(1+S[L-1]+1), count+P[L-1]+1)
    else:
        return count + P[L]


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

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

    ans = f(P, S, N, X, 0)
    print(ans)


if __name__ == "__main__":
    main()

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())
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):
n,x=map(int,input().split())
a,p=[1],[1]
for i in range(n+1):
    a.append(3+2*a[-1])
    p.append(1+2*p[-1])
def f(l,x):
    if l==0:return int(x>=1)
    if x<=1+a[l-1]:
        return  f(l-1,x-1)
    else:return p[l-1]+1+f(l-1,x-2-a[l-1])
print(f(n,x))

Solution (Python):

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






def rec(n, x):

    if n==0: return 1  
    if x==1: return 0  

    all = (1<<(n+1)) - 3  
    p = (1<<(n)) - 1  
    
    
    if x <= all + 1: return rec(n-1, x-1)  
    if x == all + 2: return p + 1  
    if x <= all * 2 + 2: return p + 1 + rec(n-1, x-all-2)  
    if x == all * 2 + 3: return p * 2 + 1  
    return -1000000

print(rec(N, X))

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


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


print(paty(n, x))

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

size = [1]
np = [1]

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

l = 0
r = size[-1]
lv = n

ans = 0

while True:
    
    mid = (l + r) // 2
    if x == mid:
        ans += np[lv-1] + 1
        break
    elif x == l:
        break
    elif x == r:
        ans += np[lv]
        break
    
    if x < mid:
        l += 1
        r = mid - 1
    else:
        ans += np[lv-1] + 1
        l = mid + 1
        r -= 1

    lv -= 1

print(ans)

Solution (Python):
n,x=map(int,input().split())
p=[1]
q=[1]
for i in range(n):
    p.append(2*p[i]+1)
    q.append(2*q[i]+3)
def cal(n_cal,x_cal):
    if x_cal==0:
        ret=0
    elif n_cal==0 and x_cal==1:
        ret=1
    elif x_cal==1:
        ret=0
    elif 1<x_cal<=q[n_cal-1]+1:
        ret=cal(n_cal-1,x_cal-1)
    elif  q[n_cal-1]+2==x_cal:
        ret=(p[n_cal-1]+1)
    elif x_cal<=2+q[n_cal-1]*2:
        ret=p[n_cal-1]+1+cal(n_cal-1,x_cal-(q[n_cal-1]+2))
    elif x_cal==3+2*q[n_cal-1]:
        ret=2*p[n_cal-1]+1
    return ret
print(cal(n,x))

Solution (Python):
N, X = map(int,input().split())
def dfs(L, X):
    if X == 1:
        if L == 0:
            return 1
        else:
            return 0
    elif 2 <= X <= 2 ** (L + 1) - 2:
        return dfs(L - 1, X - 1)
    elif X == 2 ** (L + 1) - 1:
        return 2 ** L
    elif 2 ** (L + 1) <= X <= 2 ** (L + 2) - 4:
        return 2 ** L + dfs(L-1, X - 2 ** (L + 1) + 1)
    else:
        return 2 ** (L + 1) - 1
print(dfs(N, X))

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

    print(getAns(N,X))

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

if __name__ == '__main__':
    solve()

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

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

dp = [dict() for _ in range(n+1)]
dp[0][1] = 1
dp[0][0] = 0


def solve(i, j):
    if j in dp[i]:
        return dp[i][j]

    if i == 0:
        return dp[i][j]

    if j == 0:
        return 0

    val = 0
    if s[i] <= j:
        val = solve(i-1, s[i-1]) * 2 + 1
    elif s[i-1] + 2 <= j:
        val = solve(i-1, s[i-1]) + 1 + solve(i-1, j-s[i-1]-2)
    else:
        val = solve(i-1, j-1)

    dp[i][j] = val
    return val


print(solve(n, x))

Solution (Python):
n, x = map(int, input().split())
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 1 - (x <= 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):
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:
        return 0
    elif x <= l[n - 1] + 1:
        return f(n - 1, x - 1)
    elif x == l[n - 1] + 2:
        return p[n - 1] + 1
    elif x <= 2 * l[n - 1] + 2:
        return p[n - 1] + 1 + f(n-1, x - 2 - l[n - 1])
    else:
        return 2 * p[n - 1] + 1
print(f(n, x))

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

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

b_memo=[0]*51
p_memo=[0]*51
b_memo[0]=1
p_memo[0]=1

for i in range(50):
    b_memo[i+1]=b_memo[i]*2+3
    p_memo[i+1]=p_memo[i]*2+1
    
print(f(n,x))

Solution (Python):
def make(n,x):
    if n==0:
        return 1
    elif x==1:
        return 0
    elif x==b_memo[n-1]+2:
        return p_memo[n-1]+1
    elif x>b_memo[n-1]+1:
        return p_memo[n-1]+1+make(n-1,x-b_memo[n-1]-2)
    else:
        return make(n-1,x-1)
  
n,k=map(int,input().split())
b_memo=[0]*51
p_memo=[0]*51
b_memo[0]=1
p_memo[0]=1
for i in range(50):
    b_memo[i+1]=2*b_memo[i]+3
for i in range(50):
    p_memo[i+1]=2*p_memo[i]+1

print(make(n,k))

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

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

memo = {}


def calc(N, X):
    if (N, X) in memo:
        return memo[N, X]

    if not 1 <= X <= nums[N]:
        return 0
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif X <= nums[N - 1] + 1:
        memo[N, X] = calc(N - 1, X - 1)
    elif X <= nums[N - 1] + 2:
        memo[N, X] = calc(N - 1, nums[N - 1]) + 1
    elif X < 2 * nums[N - 1] + 2:
        memo[N, X] = calc(N - 1, nums[N - 1]) + 1 + calc(N - 1, X - nums[N - 1] - 2)
    else:
        memo[N, X] = 2 * calc(N - 1, nums[N - 1]) + 1
    return memo[N, X]


print(calc(N, X))

Solution (Python):

"""
Created on Mon Apr 27 21:30:42 2020
"""

import sys


sys.setrecursionlimit(10 ** 9)


mod = 10**9+7


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


n = N
eat = X

def dfs(x):
    x

ans = 0

while eat > 0 and n >= 0:
    if eat == (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat = 0
        n -= 1
    elif eat > (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat -= (pow(2,n+2) - 2) //2
        n -= 1
    else:
        eat -= 1
        n -= 1


print(ans)

Solution (Python):
inf = 10**9+7
mod = 10**9+7
n,x = map(int, input().split())
dp_s = [0 for i in range(n+1)]
dp_p = [0 for i in range(n+1)]
dp_s[0] = 1
dp_p[0] = 1
for i in range(n):
    dp_s[i+1] = dp_s[i]*2+3
for i in range(n):
    dp_p[i+1] = dp_p[i]*2+1

def getP(dim, rest):
    if dim == 0:
        if rest == 0:
            return 0
        elif rest == 1:
            return 1
    if rest == 1:
        return 0
    elif 1 < rest < dp_s[dim-1]+2:
        return getP(dim-1, rest-1)
    elif rest == dp_s[dim-1]+2:
        return dp_p[dim-1]+1
    elif dp_s[dim-1]+2 < rest < dp_s[dim]:
        return dp_p[dim-1]+1+getP(dim-1, rest-(dp_s[dim-1]+2))
    elif rest == dp_s[dim]:
        return dp_p[dim]

print(getP(n, x))

Solution (Python):
import sys
import math  
import bisect  
import queue  


def input():
    return sys.stdin.readline().rstrip()


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


if __name__ == '__main__':
    main()

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, X = lr()
burger = [0] * (N+1)
burger[0] = 1
patty = [0] * (N+1)
patty[0] = 1
for i in range(1, N+1):
    burger[i] = burger[i-1] * 2 + 3
    patty[i] = patty[i-1] * 2 + 1

def solve(N, take):
    """レベルNバーガーのtake層目までのpattyの数を返す"""
    if N == 0:
        return min(1, take)
    mid = burger[N] // 2 + 1
    if take == mid:
        return patty[N-1] + 1
    if take > mid:
        return patty[N-1] + 1 + solve(N-1, take-mid)
    else:
        return solve(N-1, max(0, take-1))

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

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

n = [1]
p = [1]

for i in range(1, N+1):
    n.append(n[-1] * 2 + 3)
    p.append(p[-1] * 2 + 1)
    
lev = N
n1 = [0, 1, 2, 3, 3]
ans = 0

while lev >= 0:
    if lev ==0:
        ans += 1
        break
    if n[lev]//2 + 2 <= x:
        ans += p[lev-1] + 1
        x -= n[lev-1] + 2
    elif n[lev]//2 + 1 == x:
        ans += p[lev-1] + 1
        break
    elif x==1:break
    else: x -= 1

    lev -= 1
 
print(ans)

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


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

print(func(N, X))

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


ans = 0
def Xmas(n,x):
    global ans
    if n == 0 or x == ln[n] or x == 1 or x == (ln[n]+1) // 2:
        if n == 0:
            return ans + 1
        elif x == 1:
            return ans
        elif x == ln[n]:
            return ans + p[n]
        elif x == ((ln[n]+1) // 2):
            return ans + p[n-1] + 1
    else:
        if x < ((ln[n] +1)// 2):
            return Xmas(n-1,x-1)
        else:
            ans += (p[n-1] + 1)
            return Xmas(n-1,x-(ln[n-1] + 2))
print(Xmas(n,x))

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

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


def check(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + a[n - 1]:
        return check(n - 1, x - 1)
    else:
        return b[n - 1] + check(n - 1, x - 2 - a[n - 1]) + 1


print(check(n, x))

Solution (Python):

import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, X = lr()
burger = [0] * 51 
burger[0] = 1
patty = [0] * 51
patty[0] = 1
for i in range(1, N+1):
    burger[i] = 2 * burger[i-1] + 3
    patty[i] = 2 * patty[i-1] + 1


answer = 0
while X:
    if N == 0:
        answer += 1
        break
    if X <= 1:
        break
    elif X == burger[N]:
        answer += patty[N]
        break
    if X > burger[N] // 2:
        answer += patty[N-1] + 1  
        X -= burger[N-1] + 2
        N -= 1
        continue
    else:
        X -= 1
        N -= 1

print(answer)

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

def dfs(level,z):
    if level==0:
        return 0 if z<=0 else 1
    elif z<=(1+atsusa[level-1]):
        return dfs(level-1,z-1)
    else:
        return 1+pati_kazu[level-1]+dfs(level-1,z-2-atsusa[level-1])

print(dfs(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 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(1, N+1):
  a.append(2 * a[i-1] + 3)
  p.append(2 * p[i-1] + 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 f(N-1, X-a[N-1]-2) + p[N-1] + 1
  
print(f(N, X))

Solution (Python):
def f(i, X):
    if i == 0:
        return 1

    elif X == 1:
        return 0

    elif X <= 1 + a[i-1]:
        return f(i-1, X-1)

    elif X == 2 + a[i-1]:
        return p[i-1] + 1

    elif X <= 2 + 2 * a[i-1]:
        return f(i-1, X-2-a[i-1]) + 1 + p[i-1]

    else:
        return p[i]

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

print(f(N, X))

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

tmp_p = 1
tmp_v = 1
p_li = [1]
v_li = [1]
b0_li = [0,1,2,3,3]

for i in range(n):
    tmp_p = tmp_p * 2 + 1
    tmp_v = tmp_v * 2 + 3
    p_li.append(tmp_p)
    v_li.append(tmp_v)

def dfs(x,sou,num):
    
    if x == v_li[sou]:
        print(num+p_li[sou])
        return
    elif x == 1:
        print(num)
        return
    elif x <= v_li[sou-1]+1:
        if sou == 2:
            print(num+b0_li[x-2])
            return
        else:
            
            dfs(x-1,sou-1,num)
    elif x == v_li[sou-1] + 2:
        print(num+p_li[sou-1]+1)
        return
    elif x <= 2*v_li[sou-1]+2:
        dfs(x-2-v_li[sou-1],sou-1,num+p_li[sou-1]+1)

dfs(x,n,0)

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


def calc(L, X):
    
    if X <= 0:
        return 0
    elif L == 0:
        return X

    if X <= size[L - 1] + 1:
        
        return calc(L - 1, X - 1)
    elif X < 2 * size[L - 1] + 2:
        
        return full_pt[L - 1] + 1 + calc(L - 1, X - 2 - size[L - 1])
    else:
        return full_pt[L]

print(calc(N, X))

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

def eat(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 1
    mid = layers[n-1] + 2
    if x < mid:
        return eat(n-1, x-1)
    return 1 + patties[n-1] + eat(n-1, x-mid)

print(eat(N, X))

Solution (Python):
from functools import lru_cache

@lru_cache()
def p(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    n_ = 2**(n + 1) - 1
    if x == n_:
        return 2**n
    if x > n_:
        return p(n - 1, x - n_) + 2**n
    return p(n - 1, x - 1)

def main():
    print(p(*map(int, input().split())))

if __name__ == '__main__':
    main()

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


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

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

print(f(n,x))

Solution (Python):
from functools import reduce
n_,x_=map(int,input().split())
a=[1]
p=[1]
for i in range(n_):
    a.append(2*a[-1]+3)
    p.append(2*p[-1]+1)

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

print(f(n_,x_))

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


def func(level, x):
    if level == 0:
        return 0 if x <= 0 else 1
    if burger[level-1] + 1 < x:
        return func(level-1, x-burger[level-1]-2) + patty[level-1] + 1
    else:
        return func(level-1, x-1)


print(func(N, X))

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