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

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float("INF")


def solve():

    N, X = LI()

    def dfs(n, x):
        if x == 1 and n > 0:
            return 0
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n
    print(dfs(N, X))
    return



if __name__ == '__main__':
    solve()

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

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

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

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

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

print(rec(N,X))

Solution (Python):
n,x=map(int,input().split())
B=[1] 
P=[1] 
for i in range(n-1):
    B.append(B[-1]*2+3)
    P.append(P[-1]*2+1)
ans=0
for i in range(n):
    if x==1:
        break
    elif 1<x<B[n-i-1]+2:
        x-=1
    elif x==B[n-i-1]+2:
        ans+=P[n-i-1]+1
        break
    elif x>B[n-i-1]+2:
        ans+=P[n-i-1]+1
        x-=B[n-i-1]+2
    else:
        ans+=2*P[n-i-1]+1
        break
else:
    ans+=1
print(ans)

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







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

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

def bgsize(n):
  return 2 ** (n+2) - 3

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

lv1 = 'BPPPB'
ans = 0
pos = 0
lv = n
eat = False

while True:

  if pos == x:
    break

  if eat:
    ans += 1
    pos += 1
    eat = False
    continue

  if lv ==1 and x - pos < 5:
    ans += lv1[:x-pos].count('P')
    break

  if pos + bgsize(lv) <= x:
    ans += patty(lv)
    pos += bgsize(lv)
    eat = True
  else:
    pos += 1
    lv -= 1

print(ans)

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

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

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

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

def burger(n,x):
  if n==0:
    return 1
  
  l=W[n-1]
  if x==1:
    return 0
  if x==W[n]:
    return P[n]
  if x==1+l+1:
    return P[n-1]+1
  if 1<x<=l+1:
    return burger(n-1,x-1)
  if 1+l+1<x<=1+l+1+l:
    return P[n-1]+1+burger(n-1,x-(l+2))
  
print(burger(N, X))

Solution (Python):

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

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



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

print(solv(n,x))

Solution (Python):
def bg(n,x):
    if n==0:return 1
    l = wid[n-1]
    if x==1:return 0
    if 1<x<=l+1:
        return bg(n-1,x-1)
    if x==l+2:
        return pat[n-1]+1
    if l+2<x<=2*l+2:
        return pat[n-1]+1 + bg(n-1,x-l-2)
    if x==2*l+3 :
        return pat[n]

wid = [1]*51
for i in range(1,51):
    wid[i] = 2*wid[i-1]+3
pat = [1]*51
for i in range(1,51):
    pat[i] = pat[i-1]*2+1
n,x = map(int,input().split())
print(bg(n,x))

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

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

"""
　　レベルnの層数：a_0 = 1 , a_n = 2*a_(n-1)+3
レベルnのパティ数：b_0 = 1 , b_n = 2*b_(n-1)+1
"""

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

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

def ans(n,x):
    if n == 0:
        return 1
    else:
        if x == 1:
            return 0
        if 1 < x <= thickness(n-1)+1:
            return ans(n-1,x-1)
        if x == thickness(n-1) + 2:
            return patty(n-1) + 1
        if thickness(n-1) + 2 < x <= 2 * thickness(n-1) + 2:
            return patty(n-1) + 1 + ans(n-1,x-2-thickness(n-1))
        if x == 2 * thickness(n-1) + 3:
            return 2 * patty(n-1) + 1

print(ans(N,X))

Solution (Python):
n,x=map(int,input().split())
a=1
b=1
sou=[a] 
patty=[b] 
for i in range(49):
    a=(3+2*a)
    b=(1+2*b)
    sou.append(a)
    patty.append(b)
zan=x
total=0 
ok=0
def check(num): 
    global zan,total,ok
    if ok==1:
        return
    for i in range(5):
        if i==0 or i==4:
            zan-=1
        elif i==2:
            zan-=1
            total+=1
        else:
            zan-=sou[num-1]
            total+=patty[num-1]
        if zan==0:
            ok=1
            return
        elif zan<0:
            total-=patty[num-1]
            zan+=sou[num-1]
            
            check(num-1)
            if ok==1:
                break
check(n)
print(total)

Solution (Python):
def main():

    burgur = [0] * 51
    burgur[0] = 1
    pate = [0] * 51
    pate[0] = 1
    for i in range(50):
        burgur[i+1] = burgur[i] * 2 + 3
        pate[i+1] = pate[i] * 2 + 1
    
    N, X = map(int, input().split())

    X -= 1
    ans = 0
    for i in reversed(range(1, N+1)):
        if X == burgur[i] - 1:
            ans += pate[i]
            break
        elif X >= burgur[i-1] + 1:
            ans += pate[i-1] + 1
            X -= (burgur[i-1] + 2)
        else: 
            X -= 1
    if X == 0:
        ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Solution (Python):
import sys

def MultiBurger(n,x):
    """
    レベルnバーガーの下からx枚に含まれるパティの量を計算する関数
    nBurger = 0 + n-1Burger + 1 + n-1Burger + 0
    0Burger = 1
    b=0
    p=1
    """
    sum=( 1<<n+2 )-3
    
    middle=( 1<<n+1 )-1
    
    num=(middle-1)//2
    

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

    elif x<middle-1:
        return MultiBurger(n-1,x-1)
    elif x==middle-1:
        return num
    elif x==middle:
        return num+1
    elif middle<x<sum-1:
        return num+1+MultiBurger(n-1,x-middle)
    else:
        return num*2+1
    
INPUT=input().split()
N=int(INPUT[0])
X=int(INPUT[1])
Paty=MultiBurger(N,X)

print(Paty)

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

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

def len(i):
    return B[i] + P[i]

def f(l, x):
    if l == 0:
        return 1
    if x == 1:
        return 0
    if x <= len(l - 1) + 1:
        return f(l - 1, x - 1)
    if x == len(l - 1) + 2:
        return P[l - 1] + 1
    if x <= len(l - 1) * 2 + 2:
        return P[l - 1] + f(l - 1, x - (len(l - 1) + 2)) + 1
    return P[l]

print(f(N, X))

Solution (Python):
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: int, x: int) -> int:
    """レベルnバーガーの下からx枚のパティの数
    """
    if x == 1:
        return 0 if n > 0 else 1
    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] + 2:
        return p[n-1] + 1 + f(n-1, x - (2+a[n-1]))
    elif x == 2*a[n-1] + 3:
        return p[n]
    else:
        raise ValueError("xがレベルnバーガーの厚さより大きい, x={}, n={}".format(x, n))


if __name__ == "__main__":
    ans = f(N, X)
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 

def ii(): return int(sys.stdin.readline().rstrip()) 
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) 
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]

def ss(): return sys.stdin.readline().rstrip() 
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) 
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]




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

Solution (Python):
def main():
    N, X = (int(i) for i in input().split())

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

    def dfs(n, x):
        a = A[n]
        b = B[n-1]
        if n == 0:
            return 1
        elif n >= x:
            return 0
        elif x == a//2:
            return b
        elif x == a//2 + 1:
            return b + 1
        elif x < a//2:
            return dfs(n-1, x-1)
        elif x > a//2 + 1:
            return dfs(n-1, x-(a//2)-1) + (b + 1)

    print(dfs(N, X))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, X = (int(i) for i in input().split())
    ans = 0

    def dfs(n, x, ans):
        a = 1 + 4*(2**n - 1)
        if n == 0:
            return 1
        elif n >= x:
            return 0
        elif x == a//2:
            return 1 + 2*(2**(n-1) - 1)
        elif x == a//2 + 1:
            return 1 + 2*(2**(n-1) - 1) + 1
        elif x < a//2:
            ans += dfs(n-1, x-1, ans)
        elif x > a//2 + 1:
            ans += dfs(n-1, x-(a//2)-1, ans) + (1 + 2*(2**(n-1) - 1) + 1)
        return ans

    print(dfs(N, X, ans))


if __name__ == '__main__':
    main()

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

L = [0]*(N+1)
L[0] = 1

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


def solve(n, x):
    
    if x == L[n]:
        return(P[n])
    elif x <= n:
        return(0)
    else:
        ret = 0
        if x >= L[n-1] + 1:
            ret += P[n-1]
            x -= L[n-1] + 1
            if x > 0:
                ret += 1 + solve(n-1, x - 1)
        else:
            ret = solve(n-1, x-1)
        return(ret)


print(solve(N, X))

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**9)
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 <= a[n-1] + 1:
        return f(n-1, x-1)
    else:
        return p[n-1] + 1 + f(n-1, x-2-a[n-1])

print(f(N, X))

Solution (Python):
def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

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

    size = [0] * (N + 1)
    patty = [0] * (N + 1)
    size[0] = 1
    patty[0] = 1
    for lv in range(1, N + 1):
        size[lv] = size[lv - 1] * 2 + 3
        patty[lv] = patty[lv - 1] * 2 + 1

    @lru_cache(maxsize=None)
    def burger(lv, x):
        if lv == 0:
            return int(x > 0)

        if x <= 1:
            return 0

        if x <= 1 + size[lv - 1]:
            return burger(lv - 1, x - 1)

        if x == 1 + size[lv - 1] + 1:
            return patty[lv - 1] + 1

        if x <= 1 + size[lv - 1] + 1 + size[lv - 1]:
            return patty[lv - 1] + 1 + burger(lv - 1, x - (1 + size[lv - 1] + 1))

        return patty[lv]

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


if __name__ == '__main__':
    main()

Solution (Python):
from functools import lru_cache

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

@lru_cache(maxsize=None)
def length(level):
    if level <= 0:
        return 1
    return length(level - 1) * 2 + 3

@lru_cache(maxsize=None)
def search(level, right):
    if level == 0:
        return 1

    ret = 0
    right -= 1
    if length(level - 1) <= right:
        ret += search(level - 1, length(level - 1))
        right -= length(level - 1)

        if right > 0:
            ret += 1
        right -= 1

    if 0 < right:
        ret += search(level - 1, right)
    return ret

print(search(N, X))

Solution (Python):
n,x = map(int,input().split())
fi = x-1
aa = [1]
bb = [1]
a = 1
b = 1
for i in range(50):
    a = a*2 + 3
    b = b*2 + 1
    aa.append(a)
    bb.append(b)
    
def bu(lv , x):
    if lv == 0:
        return 1
    
    l = aa[lv-1]
    num = bb[lv-1]
    
    if x == 1:
        return 0
    elif x <= l+1:
        return bu(lv-1,x-1)
    elif x == l+2:
        return num +1
    elif x <= (l+1) * 2:
        return num + 1 + bu(lv-1,x-l-2)
    else:
        return num*2 + 1
    
print(bu(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 + 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):
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

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 SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    memo={}
    def f(lv,x):
        if lv==0:return 1
        if x==1:return 0
        if x==ss[lv]:return pp[lv]
        if (lv,x) in memo:return memo[lv,x]
        if x<=ss[lv-1]+1:res=f(lv-1,x-1)
        elif x==ss[lv-1]+2:res=pp[lv-1]+1
        else:res=pp[lv-1]+f(lv-1,x-ss[lv-1]-2)+1
        memo[lv,x]=res
        return res

    ss=[1]
    pp=[1]
    for i in range(50):
        ss.append(ss[-1]*2+3)
        pp.append(pp[-1]*2+1)
    
    
    n,x=MI()
    print(f(n,x))



main()

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



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


def f(l, x):
    if l==0:
        if x>0:
            return 1
        else:
            return 0
    
    elif x<=a[l-1]+1:
        return f(l-1, x-1)

    else:
        return p[l-1] + 1 + f(l-1, x-a[l-1]-2)

print(f(n,x))

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

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

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

print(f(N, X))

Solution (Python):
def make_burger(i, x):
    if i == 0:
        return 1 if x > 0 else 0
    mid = (b[i] + 1) // 2
    if mid > x:
        return make_burger(i - 1, x - 1)
    elif mid == x:
        return p[i - 1] + 1
    else:
        return p[i - 1] + 1 + make_burger(i - 1, x - mid)
    

n, x = map(int, input().split())
p = [1]
b = [1]

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

print(make_burger(n, x))

Solution (Python):
def main():
    N, X = (int(i) for i in input().split())
    ans = 0

    def dfs(n, x, ans):
        a = 1 + 4*(2**(n-1) - 1)
        if n == 1:
            return 1
        elif (n-1) >= x:
            return 0
        elif x == a//2:
            return 1 + 2*(2**(n-2) - 1)
        elif x == a//2 + 1:
            return 1 + 2*(2**(n-2) - 1) + 1
        elif x < a//2:
            ans += dfs(n-1, x-1, ans)
        elif x > a//2 + 1:
            ans += dfs(n-1, x-(a//2)-1, ans) + (1 + 2*(2**(n-2) - 1) + 1)
        return ans

    print(dfs(N+1, X, ans))


if __name__ == '__main__':
    main()

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

def f(n,x):
  if n==0:
    if x>0:return 1
    else:return 0
  if x<=(2**(n+2)-3-1)//2:
    return f(n-1,x-1)
  else:
    tmp=x-((2**(n+2)-3-1)//2+1)
    return 2**n-1+1+f(n-1,tmp)
  
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())

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

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


def f(fn,fx):
    if fn == 0 and fx == 1:
        return 1
    elif fx == 1:
        return 0
    elif fx == q[fn]:
        return p[fn]
    elif fx == q[fn]//2+1:
        return 1+p[fn-1]
    elif 1 < fx < q[fn]//2+1:
        return f(fn-1, fx-1)
    else:
        return p[fn-1] + 1 + f(fn-1, fx-(q[fn-1]+2))


print(f(n,x))

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def func(level, x):
    debug(level, x)
    if level == 0 and x == 1:
        return 1
    elif level == 0 and x <= 0:
        return 0
    npast = num[level - 1]
    if x <= npast + 1:
        tmp = func(level - 1, x - 1)
        debug('a', level, x, tmp)
        return tmp
    elif x == npast + 2:
        tmp = func(level - 1, x - 2)
        debug('b', level, x, tmp + 1)
        return tmp + 1
    else:
        tmp1  = num2[level - 1]
        debug('tmp1', tmp1)
        if x == npast * 2 + 3:
            debug('aa', x - npast - 3)
            tmp2 = func(level - 1, x - npast - 3)
        else:
            tmp2 = func(level - 1, x - npast - 2)
        debug('c', level, x, tmp1 + 1 + tmp2)
        return tmp1 + 1 + tmp2

n, x = MAP()
num = [1]
for i in range(2, n + 1):
    num.append(2 * num[-1] + 3)
num2 = [1]
for i in range(2, n + 1):
    num2.append(2 * num2[-1] + 1)
debug(num)
debug(num2)
ans = func(n, x)
print(ans)

Solution (Python):
def dfs(l,x):
    if x == 0:
        return 0
    if l == 0:
        return 1
    if x == 1:
        return 0
    if x <= num[l] // 2:
        return dfs(l-1,x-1)
    if x == num[l]:
        x -= 1
    return patty[l-1] + 1 + dfs(l-1,x-num[l]//2-1)
n,x = map(int,input().split())
patty = [1]
num = [1]
for i in range(1,51):
    patty.append(patty[i-1]*2+1)
    num.append(num[i-1]*2+3)
print(dfs(n,x))

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

def burger_patty_num(N):
    if N == 0:
        return 1
    return 1+ 2 * burger_patty_num(N - 1)

def patty_num(N, X):
    if X == 0:
        return 0
    if N == 0:
        return 1
    if X <= 1 + burger_size(N - 1):
        return patty_num(N - 1, X - 1)
    elif X == 2 + burger_size(N - 1):
        return 1 + burger_patty_num(N - 1)
    elif X <= 2 + 2 * burger_size(N - 1):
        return 1 + burger_patty_num(N - 1) + patty_num(N - 1, X - (2 + burger_size(N - 1)))
    else:
        return 1 + 2 * burger_patty_num(N - 1)
        
    
N, X = map(int, input().split())
print(patty_num(N, X))

Solution (Python):

from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,x = LI()
    l = [4*2**i-3 for i in range(n+1)]
    s = [2*2**i-1 for i in range(n+1)]
    ans = 0
    while x:
        if x == l[n]:
            ans += s[n]
            break
        if x <= l[n-1]+1:
            n -= 1
            x -= 1
        elif x < l[n]:
            ans += 1+s[n-1]
            x -= 2+l[n-1]
            n -= 1
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
def layers(n):
    result = 1
    for _ in range(0, n):
        result = result * 2 + 3
    return result


def meat(n):
    result = 1
    for _ in range(0, n):
        result = result * 2 + 1
    return result


def calc(n, x):
    before_layer = layers(n - 1)
    before_meat = meat(n - 1)
    if x == 1:
        return 1 if n == 0 else 0
    elif x <= 1 + before_layer:
        return calc(n - 1, x - 1)
    elif x == 2 + before_layer:
        return 1 + before_meat
    elif x <= 2 + 2 * before_layer:
        return 1 + before_meat + calc(n - 1, x - 2 - before_layer)
    elif x == 3 + 2 * before_layer:
        return 2 * before_meat + 1


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


if __name__ == '__main__':
    main()

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

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

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

print(f(N, X))

Solution (Python):
import numpy as np
import collections
N, X = list(map(int,input().split()))

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

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

print(f(N, X))

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

def solve(n,x,ans):
    if x == 0:
        return ans
    if n == 0:
        return ans + 1
    mid = layer_n[n]//2 + 1
    if x < mid:
        return solve(n-1,x-1,ans)
    elif x == mid:
        return ans + P_n[n-1]+1
    else:
        x -= 2 + layer_n[n-1]
        ans += P_n[n-1]+1
        return solve(n-1,x,ans)

print(solve(N,X,0))

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

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

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

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

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

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

    
    def solve(n, x):
        if n==0:
            if x==0:
                return 0
            else:
                return 1
        res = 0
        if b[n]//2 == x:
            res += p[n-1]
        elif b[n] == x:
            res += p[n-1]*2 + 1
        elif x == 0:
            res = 0
        elif b[n]//2 < x:
            res += p[n-1] + 1 + solve(n-1, x-b[n]//2-1)
        else:
            res += solve(n-1, x-1)
        return res

    print(solve(n, x))

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

g = [1] * 51
p = [1] * 51

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


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

    if x <= g[n - 1] + 1:
        return rec(n - 1, x - 1)
    elif x == g[n - 1] + 2:
        return p[n - 1] + 1
    elif x <= 2 * g[n - 1] + 2:
        return rec(n - 1, x - g[n - 1] - 2) + p[n - 1] + 1
    else:
        return p[n]


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

Solution (Python):
N,X=map(int,input().split(' '))
l = 1
p = 1
L=[]
P=[]
for i in range(N):
    l = 2*l+3
    p = 2*p+1
    L.append(l)
    P.append(p)
def pans(l,x):
    if l==1:
        return list('BPPPB'[:x]).count('P')
    elif x<=L[l-2]+1:
        return pans(l-1,x-1)
    else:
        return P[l-2]+1+pans(l-1,x-(2+L[l-2]))
print(pans(N,X))

Solution (Python):

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    
            

    for d in directions:
        nx = d+x
        
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,X=acinput()

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

def f(N,k):
    
        
    if N == 0 and k>=1:
        return 1
    
    if k <= 1:
        return 0
    
    if k<=n[N-1]+1:
        return f(N-1,k-1)
    else:
        r=k-n[N-1]-2
        return p[N-1]+f(N-1,r)+1


print(f(N,X))

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

def make_burger(i, x):
    if i == 0:
        return 1 if x >= 1 else 0
    center_num = (a[i] + 1) // 2
    if center_num > x:
        return make_burger(i - 1, x - 1)
    elif center_num == x:
        return p[i - 1] + 1
    else:
        return p[i - 1] + 1 + make_burger(i - 1, x - center_num)


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

print(make_burger(n, x))