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


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

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

sizes = [1]

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

prev = {}

def solve(n, x):
    if (n, x) in prev:
        return prev[(n, x)]
    else:
        if n == 0:
            return 1 if x == 1 else 0
        else:
            ans = 0
            if x == sizes[n]:
                ans = 2*solve(n-1, sizes[n-1]) + 1
            else:
                mid = sizes[n]//2 + 1

                if x == mid:
                    ans = solve(n-1, sizes[n-1]) + 1
                elif x < mid:
                    ans = solve(n-1, x-1)
                else:
                    ans = solve(n-1, sizes[n-1]) + 1 + solve(n-1, x-mid)

            prev[(n, x)] = ans
            return ans

print(solve(n, x))

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
N, X = map(int, input().split())

layers = [1]
patties = [1]

for i in range(1, N+1):
	layer_i = 2 * layers[i-1] + 3
	patty_i = 2 * patties[i-1] + 1
	layers.append(layer_i)
	patties.append(patty_i)
	
def f(n, x):
	if x == 1:
		return 1 if n == 0 else 0
		
	elif 1 < x <= 1 + layers[n-1]:
		return f(n-1, x-1)
		
	elif x == 2 + layers[n-1]:
		return patties[n-1] + 1
		
	elif 2 + layers[n-1] < x <= 2 + 2 * layers[n-1]:
		return patties[n-1] + 1 + f(n-1, x-2-layers[n-1])
		
	else:
		return 2 * patties[n-1] + 1
		
print(f(N, X))

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

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

    ans = 0
    for _ in range(n):
        if x == 0:
            break
        if x >= pb[-2] + 2:
            x -= pb[-2] + 2
            ans += 1 + p[-2]
        else:
            x -= 1
        pb.pop(-1)
        p.pop(-1)

    if x >= 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):








def solve(N, X):
    layer = [1]
    pate = [1]
    for _ in range(N):
        layer.append(layer[-1] * 2 + 3)
        pate.append(pate[-1] * 2 + 1)

    
    

    def burger(n, l):
        if layer[n] <= l:
            return pate[n]
        if l == 0:
            return 0
        re = 0
        if layer[n] // 2 + 1 <= l:
            re += pate[n - 1] + 1  
            l -= layer[n] // 2 + 1
        else:
            l -= 1  
        re += burger(n - 1, l)
        return re

    print(burger(N, X))


if __name__ == '__main__':
    N, X = map(int, input().split())
    solve(N, X)

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

print(solve(N,X))

Solution (Python):
def delete_head_zeros(n):
	n = str(n)
	l = len(n)
	if "." in n:
		l = n.find(".")
	head_zeros = 0
	for i in range(l - 1):
		if n[i] == "0":
			head_zeros += 1
		else:
			break

	return n[head_zeros:]



def bigint_compare(a, b):
	a = delete_head_zeros(a)
	b = delete_head_zeros(b)
	if len(a) > len(b):
		return 1
	elif len(a) < len(b):
		return -1
	else:
		if a > b:
			return 1
		elif a < b:
			return -1
		else:
			return 0



def bigint_plus(a, b):
	a = str(a)
	b = str(b)

	d = max([len(a), len(b)])
	a = '0' * (d - len(a)) + a
	b = '0' * (d - len(b)) + b

	ans = ""
	carry = 0
	for i in range(d):
		s = int(a[-i-1]) + int(b[-i-1]) + carry
		carry = s // 10
		ans = str(s % 10) + ans
	else:
		if carry:
			ans = str(carry) + ans

	return ans



def bigint_minus(a, b): 
	a = str(a)
	b = str(b)
	M = []
	m = []
	sign = ""

	if len(a) > len(b) or (len(a) == len(b) and a >= b):
		[M, m] = [a, b]
	else:
		[M, m] = [b, a]
		sign = "-"
	m = '0' * (len(M) - len(m)) + m

	ans = ""
	borrow = 0
	for i in range(len(M)):
		s = int(M[-i-1]) - int(m[-i-1]) - borrow
		if s < 0:
			borrow = 1
			s += 10
		else:
			borrow = 0
		ans = str(s) + ans

	return sign + delete_head_zeros(ans)



def bigint_multiply(a, b):
	a = str(a)
	b = str(b)

	md = []
	for j in range(len(b)):
		carry = 0
		mj = ""
		for i in range(len(a)):
			m = int(a[-i-1]) * int(b[-j-1]) + carry
			carry = m // 10
			mj = str(m % 10) + mj
		else:
			if carry:
				mj = str(carry) + mj
		md.append(mj)

	ans = 0
	for k in range(len(md)):
		ans = bigint_plus(md[k] + "0" * k, ans)

	return ans




def bigint_divide(a, b, d = 0):
	a = str(a)
	b = str(b)
	d = int(d)
	if d < 0:
		d = 0

	ans = ""
	r = ""
	for i in range(len(a) + d):
		q = 0
		if i < len(a):
			r += a[i]
		elif i == len(a):
			ans += "."
			r += "0"
		else:
			r += "0"

		if bigint_compare(r, b) == -1:
			ans += str(q)
		else:
			while bigint_compare(r, b) >= 0:
				r = bigint_minus(r, b)
				q += 1
			ans += str(q)

	return delete_head_zeros(ans)

def main():
	N, X = input().split(" ")
	layer = [1]
	patties = [1]
	for i in range(int(N)):
		layer.append(bigint_plus(bigint_multiply(layer[-1], 2), 3))
		patties.append(bigint_plus(bigint_multiply(patties[-1], 2), 1))

	def count_patty(L, Y, P): 
		if L == 0:
			return bigint_plus(P, 1)
		center = bigint_divide(bigint_plus(layer[L], 1), 2)
		if Y == "1":
			return P
		elif Y == layer[L]:
			return bigint_plus(P, patties[L])
		elif bigint_compare(Y, center) == 0:
			return bigint_plus(bigint_plus(P, 1), patties[L - 1])
		elif bigint_compare(Y, center) == 1:
			return count_patty(L - 1, bigint_minus(Y, center), bigint_plus(bigint_plus(P, patties[L - 1]), 1))
		elif bigint_compare(Y, center) == -1:
			return count_patty(L - 1, bigint_minus(Y, 1), P)

	print(count_patty(int(N), X, "0"))

main()

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

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 func(i,x):
  if i==0:
    if x<=0:
      return 0
    elif x>=1:
      return 1
  mid=(a[i]+1)//2
  if mid==x:
    return p[i-1]+1
  elif mid>x:
    return func(i-1,x-1)
  else:
    return p[i-1]+1+func(i-1,x-mid)


print(func(n,x))

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

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 func(i,x):
  if i==0:
    if x<=0:
      return 0
    elif x>=1:
      return 1
  mid=(a[i]+1)//2
  if mid==x:
    return p[i-1]+1
  elif mid>x:
    return func(i-1,x-1)
  else:
    return p[i-1]+1+func(i-1,x-mid)


print(func(n,x))

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

a, b = [1], [1]

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

def cal(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1
    val = (a[n]+1)//2

    if x < val:
        return cal(n-1, x-1)
    elif x == val:
        return b[n-1]+1
    elif x > val:
        return b[n-1]+1+cal(n-1, x-val)

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

Solution (Python):

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

    As = [1]  
    Ps = [1]  

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

    def f(n, x):
        if n == 0:
            return 0 if x <= 0 else 1
        mid = (As[n] + 1) // 2

        
        if x < mid:
            return f(n - 1, x - 1)
        elif x == mid:
            return Ps[n - 1] + 1
        elif x > mid:
            return Ps[n - 1] + 1 + f(n - 1, x - mid)

    ans = f(N, X)

    print(ans)


if __name__ == "__main__":
    resolve()

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

def f(N,X):
    if 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
import collections

sys.setrecursionlimit(10**6)

def f(X:int, N:int):
    if N == 0:
        return 1
    if N == 1:
        if X == 1:
            return 0
        elif X in [2, 3, 4]:
            return X-1
        else:
            return 3
    l = sum(L[N-1])
    if X == 1:
        return 0
    elif 1 < X <= l+1:
        return f(X-1, N-1)
    elif X == l+2:
        return L[N-1][1] + 1
    elif l+2 < X <= sum(L[N]):
        return L[N-1][1] + 1 + f(X-2-l, N-1)
    else:
        return 2 * L[N-1][1] + 1

def main():
    global L
    N, X = map(int, input().split())
    L = [(0, 1)]
    for i in range(N):
        b, p = L[i]
        b = 2*b + 2
        p = 2*p + 1
        L.append((b, p))
    ans = f(X, N)
    print(ans)

if __name__ == "__main__":
    main()

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

xx=[[1,1,1,1,1]for _ in range(N+1)]
i=0
while i+1<=N:
    xx[i+1][1]=L[i][1]+1
    xx[i+1][2]=L[i][1]+2
    xx[i+1][3]=2*L[i][1]+2
    xx[i+1][4]=2*L[i][1]+3
    i+=1

ans=0
while N>0:
    if xx[N][0]==X:
        break
    elif xx[N][1]>=X:
        N-=1
        X-=1
    elif xx[N][2]==X:
        ans+=1+L[N-1][0]
        break
    elif xx[N][3]>=X:
        ans+=1+L[N-1][0]
        X-=xx[N][2]
        N-=1
    else:
        ans+=1+2*L[N-1][0]
        break
    if N==0:
        ans+=1

print(ans)

Solution (Python):
from functools import lru_cache
N, X = map(int, input().split())
a = [0] * (N)
p = [0] * N
a[0] = 1
p[0] = 1
for i in range(1, N):
    a[i] = a[i-1]*2 + 3
    p[i] = p[i-1]*2 + 1
@lru_cache(maxsize=1000)
def f(n, x):
    if n == 0 and x == 0:
        return 0
    elif n == 0:
        return 1
    if 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):
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))



N,X=mint()
ans=0
size=[0]*51
size[0]=(1,1)
for i in range(1,51):
    size[i]=(2*size[i-1][0]+3, 2*size[i-1][1]+1)

def rec(L):
    global X,ans
    if X==0:
        return
    if L==0:
        X-=1
        ans+=1
    else:
        X-=1
        if X<size[L-1][0]:
            rec(L-1)
        else:
            X-=size[L-1][0]
            ans+=size[L-1][1]
        if X==0:
            return
        X-=1
        ans+=1
        if X<size[L-1][0]:
            rec(L-1)
        else:
            X-=size[L-1][0]
            ans+=size[L-1][1]
        if X==0:
            return
        X-=1
    
rec(N)
print(ans)

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

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

    ans = 0
    for _ in range(n):
        if x == 0:
            break
        if x >= pb[-2] + 2:
            x -= pb[-2] + 2
            ans += 1 + p[-2]
        else:
            x -= 1
        pb.pop(-1)
        p.pop(-1)

    if x >= 1:
        ans += 1

    print(ans)

main()

Solution (Python):
n, x = map(int, input().split())
b = 1
p = 1
for i in range(n):
    b = 2 * b + 3
    p = 2 * p + 1
x -= 1
b -= 1
ans = 0
while True:
    if x == 0:
        if b == 0:
            ans += 1
        break
    elif x == b:
        ans += p
        break
    elif x == b // 2:
        ans += p // 2 + 1
        break
    elif 0 < x < b // 2:
        x -= 1
    else:
        x -= b // 2 + 1
        ans += p // 2 + 1
    b = (b - 3) // 2
    p = (p - 1) // 2
print(ans)

Solution (Python):
n, x = map(int, input().split())
b = 1
p = 1
for i in range(n):
    b = 2 * b + 3
    p = 2 * p + 1
x -= 1
b -= 1
ans = 0
while True:
    if x == 0:
        if b == 0:
            ans += 1
        break
    elif x == b:
        ans += p
        break
    elif x == b // 2:
        ans += p // 2 + 1
        break
    elif 0 < x < b // 2:
        x -= 1
    else:
        x -= b // 2 + 1
        ans += p // 2 + 1
    b = (b - 3) // 2
    p = (p - 1) // 2
print(ans)

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

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

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= size[N-1] + 1:
        return f(N-1, X-1)
    elif X == size[N-1] + 2:
        return patty[N-1] + 1
    elif X >= size[N-1] + 3:
        return patty[N-1] + 1 + f(N-1, X-size[N-1]-2)
print(f(N,X))

Solution (Python):
import sys
import heapq
from functools import lru_cache
sys.setrecursionlimit(10000)


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


def level(n, k):
    number = 2 ** (n + 1) - 3  
    cn = 2**(n+2) -3
    if n == 0:
        return 1
    elif k==cn:
        return (2**(n+1) -1)

    else:
        if k == 1:
            return 0
        elif k <= 1 + number:
            return level(n - 1, k - 1)
        elif k == 2 + number:
            return level(n - 1, number) + 1
        else:
            return 1 + level(n - 1, number) + level(n - 1, min(number, k - number - 2))



def main():

    n,k=map(int,input().split())
    print(level(n,k))


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**5)
N, X = map(int,input().split())
l = [1]
for i in range(N):
    l.append(2*l[-1]+3)
d = {}
def f(n,x):
    if (n,x) in d:
        return d[(n,x)]
    if n == 0:
        ans = 1
    elif x == 1:
        ans = 0
    elif x <= l[n-1]+1:
        ans = f(n-1,x-1)
    elif x == l[n-1]+2:
        ans = f(n-1,l[n-1])+1
    elif x <= 2*l[n-1]+2:
        ans = f(n-1, l[n-1])+1+f(n-1, x-l[n-1]-2)
    else:
        ans = 2*f(n-1, l[n-1])+1
    d[(n,x)] = ans
    return ans
print(f(N, X))

Solution (Python):
import sys

from functools import lru_cache


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, x = input_int_list()
    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)

    @lru_cache(None)
    def L(level, x):
        if x == 1:
            if level == 0:
                return 1
            else:
                return 0
        l = layer_size[level - 1]
        p = p_cnt[level - 1]
        if x <= l + 1:
            return L(level - 1, x - 1)
        elif x == l + 2:
            return p + 1
        elif x <= 2 + l * 2:
            return p + 1 + L(level - 1, x - l - 2)
        else:
            return 2 * p + 1
    print(L(n, x))
    return


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

dp = [1]*(n+1)
res = 0

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

for j in range(n,1,-1):
    if dp[j] ==x:
        res += (dp[j]+1) //2
        x =0        
    elif dp[j-1]+2 <= x :
        res += 1 + (dp[j-1]+1)//2
        x -= dp[j-1]+2
    elif dp[j-1]+1 ==x:
        res += (dp[j-1]+1)//2
        x = 0
    else:
        x -=1
    
    if x ==0:
        break
        
if x ==5:
    res += 3
elif x ==0:
    pass
else:
    res +=x-1

print(res)

Solution (Python):



from collections import defaultdict

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

memo = {}

def size_lv(lv):
    if lv == 0:
        return 1
    if lv not in memo:
        memo[lv] = size_lv(lv-1) * 2 + 3
    return memo[lv]

memo2 = {}
def num_pty(lv, X):
    if (lv, X) in memo2:
        return memo2[(lv, X)]
    if X == 0:
        return 0

    if lv == 0:
        memo2[(lv, X)] = 1
        return memo2[(lv, X)]

    prevSize = size_lv(lv-1)
    if X <= prevSize+1:
        memo2[(lv, X)] = num_pty(lv-1, X-1)
        return memo2[(lv, X)]
    
    if X == prevSize + 2:
        memo2[(lv, X)] = num_pty(lv-1, prevSize) + 1
        return memo2[(lv, X)]
    
    memo2[(lv, X)] = num_pty(lv-1, prevSize) + 1 + num_pty(lv-1, min(X-prevSize-2, prevSize))
    return memo2[(lv, X)]
    
print(num_pty(N, X))

Solution (Python):

def solve(L,N):
    if L == 0:
        return 1
    if N == 1:
        return 0
    elif N <= 2**(L+1)-2:
        return solve(L-1,N-1)
    elif N == int(2**(L+1)-1):
        return 2**L
    return solve(L-1,N-2**(L+1)+1)+2**L
    

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

Solution (Python):
n,x=map(int,input().split())
c=0
def p(n):
  return 2*(2**n)-1
def f(n):
  return 4*(2**n)-3

c=0
for i in range(n,0,-1):
  if x:
    x-=1
  if x>=f(i-1):
    x-=f(i-1)
    c+=p(i-1)
    if x:
      x-=1
      c+=1
      if x>=f(i-1):
        x-=f(i-1)
        c+=p(i-1)
        if x:
          x-=1
print(c)

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

ans = 0
for i in range(N, -1, -1):
    if X < 2**(i + 1) - 1:
        X -= 1
    elif X > 2 ** (i + 1) - 1:
        X -= 2 ** (i + 1) - 1
        ans += 2 ** i
    else:
        ans += 2 ** i
        break
    if X == 0:
        break
    


print(ans)

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

def f(N,X):
  if N==0:
    return 0 if X<=0 else 1
  elif X<=1+2**(N+1)-3:
    return f(N-1,X-1)
  else:
    return 2**(N)+f(N-1,X-2**(N+1)+3-2)
        
print(f(N,X))

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

def A(N,X):
    res = 0
    if N == 0:
        return 1
    if X == 1:
        return 0
    if 1 < X <= L(N-1) + 1:
        res = A(N-1,X-1)
    elif L(N-1) + 2 == X:
        res = 1 + P(N-1)
    elif L(N-1) + 2 < X <= 2 * L(N-1) + 2:
        res = 1 + P(N-1) + A(N-1,X-(2+L(N-1)))
    elif 2 * L(N-1) + 3 == X:
        res = 1 + 2 * P(N-1)
    return res

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


if __name__ == "__main__":
    main()

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

def main(n, x, ans):
  global X
  global l
  if n == 0:
    return ans+1
  elif x==1:
    return ans
  elif x==2*l[n]-1:
    return ans+2*l[n-1]+1
  elif x == l[n]:
    return main(n-1, x-2, ans+1)
  elif x < l[n]:
    return main(n-1, x-1, ans)
  else:
    return main(n-1, x-2*l[n-1]-1, ans+l[n-1]+1)
  
a = main(N, X, 0)
print(a)

Solution (Python):
def f(L, x):
    if L == 0:
        return 0 if x <= 0 else 1
    if x <= total[L - 1] + 1:
        return f(L - 1, x - 1)
    else:
        return patties[L - 1] + 1 + f(L - 1, x - total[L - 1] - 2)


N, X = map(int, input().split())
total = [1]
patties = [1]
for i in range(50):
    total.append(total[-1] * 2 + 3)
    patties.append(patties[-1] * 2 + 1)
print(f(N, X))

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

f_dict = {
  0: 1
}
def f(n):
  if f_dict.get(n):
    return f_dict.get(n)
  return (3 + f(n-1) * 2)


patty_dict = {
  0: 1
}
def total_patty(n):
  if patty_dict.get(n):
    return patty_dict.get(n)
  return (1 + 2 * total_patty(n - 1))

def count_patty(n, x):
  if n == 0 and x == 1:
    return 1
  elif x == 0:
    return 0
  elif 1 <= x and x <= f(n - 1) + 1:
    return count_patty(n - 1, x - 1)
  elif x == f(n - 1) + 2:
    return total_patty(n - 1) + 1
  elif f(n - 1) + 2 <= x and x <= 2 * f(n - 1) + 2:
    return total_patty(n - 1) + 1 + count_patty(n - 1, x - f(n - 1) - 2)
  else:
    return total_patty(n)

print(count_patty(n, x))

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

maisu=[0]*50
pate=[0]*50
maisu[0]=1
pate[0]=1

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

def solve(l,x):
    if l==0:
        return 1
    if x<=1:
        return 0

    if x<=1+maisu[l-1]:
        return solve(l-1,x-1)
    if x==2+maisu[l-1]:
        return pate[l-1] + 1

    return pate[l-1] + 1 + solve(l-1,x-2-maisu[l-1])

print(solve(n,x))

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

t = [1]
p = [1]

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

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

print(pathi(n, x))

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

t = [1]
p = [1]

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

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

print(pathi(n, x))

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

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

h = [1]
p = [1]

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

def bug(l, y):
    if l == 0:
        return 0 if y <= 0 else 1
    
    mid = (h[l] + 1) // 2
    if y < mid:
        return bug(l - 1, y - 1)
    elif y == mid:
        return p[l - 1] + 1
    elif y > mid:
        return p[l - 1] + 1 + bug(l - 1, y - mid)
    
print(bug(N, X))

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

def rec(m, y):
    if y == 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2
    if h < y:
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)
print(rec(n, x))

Solution (Python):
memo1 = {}
def f(i):
    if i==0:
        return 1
    if i in memo1:
        return memo1[i]
    memo1[i] = 2*f(i-1)+3
    return memo1[i]
memo2 = {}
def g(i):
    if i==0:
        return 1
    if i in memo2:
        return memo2[i]
    memo2[i]=2*g(i-1)+1
    return memo2[i]
N,X = map(int,input().split())
cnt = 0
while X>0 and N>0:
    if X==f(N):
        cnt += g(N)
        X -= f(N)
    elif X>=f(N-1)+2:
        cnt += 1+g(N-1)
        X -= f(N-1)+2
    else:
        X -= 1
    N -= 1
cnt += X
print(cnt)

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

p = [0] * -~n
l = [0] * -~n

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




def rec(m, y):
    if y == 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2  
    if h < y:  
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))

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

p = [0] * -~n
l = [0] * -~n

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




def rec(m, y):
    if y <= 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2  
    if h < y:  
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))

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

p = [0] * -~n
l = [0] * -~n

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




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


print(rec(n, x))

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

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

def rec(level, K):
    if level == 0:
        return 1
    if K == 1:
        return 0
    elif K <= L[level-1] + 1:
        return rec(level-1, K-1)
    elif K == L[level-1] + 2:
        return S[level-1] + 1
    elif K <= L[level-1] * 2 + 2:
        return rec(level-1, K - L[level-1] - 2) + S[level-1] + 1;
    else:
        return S[level-1] * 2 + 1

print(rec(N, X))

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

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

f=[1]
p=[1]

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

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

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x = list(map(int, input().split()))
l = [None]*(n+1)
ps = [None]*(n+1)
v = 1
vp = 1
for i in range(n+1):
    l[i] = v
    ps[i] = vp
    v = 2*v + 3
    vp = 2*vp + 1
def sub(n,x):
    if n==0:
        if x==1:
            return 1
        else:
            return 0
    if x==1:
        return 0
    elif x==l[n]:
        return ps[n]
    elif x==l[n-1]+2:
        return ps[n-1]+1
    elif x<l[n-1]+2:
        return sub(n-1,x-1)
    else:
        return sub(n-1,x-2-l[n-1]) + ps[n-1] + 1
ans = sub(n,x)
print(ans)

Solution (Python):

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

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


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

    return p[n - 1] + 1 + func(n - 1, x - 2 - a[n - 1])


print(func(N, X))

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

def calc(n,x):
    if n==0:
        return 1 if x>0 else 0
    else:
        if x>a[n-1]+1:
            return p[n-1]+1+calc(n-1,x-2-a[n-1])
        else:
            return calc(n-1,x-1)
print(calc(n,x))