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())
ans = 0
i = n
while i >= 0:
    c = 2**(i+1) - 3
    num_p = 2**i - 1
    
    if 2*c + 3 == x:
        ans += 2*num_p + 1
        break
    elif c + 2 == x:
        ans += num_p + 1
        break
    elif 1 == x:
        break
    
    elif 2 + c <= x:
        x -= 2 + c
        ans += num_p + 1
    else:
        x -= 1
    
    i -= 1

print(ans)

Solution (Python):

import sys
input = sys.stdin.readline
N,X = (int(i) for i in input().split())
DP_all  =[0]*(N+1)
DP_p    =[0]*(N+1)
DP_all[0]   =1
DP_p[0]     =1


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




def  p_num(L,x):
    if x <=L:
        return 0
    if x ==DP_all[L]:
        return DP_p[L]
    elif x < DP_all[L] //2 +1:
        return p_num(L-1,x -1)
    elif x ==DP_all[L] //2 +1:
        return DP_p[L-1] +1
    elif x > DP_all[L] //2 +1:
        return DP_p[L-1] +1 +p_num(L-1,x -DP_all[L-1] -2)

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

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

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

print(rec(n, x))

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

ans = 0
while n >= 0:
    n -= 1
    if x == 0:
        
        if n == -1:
            ans += 1
        break
    elif 1 <= x <= lbl[n]:
        
        x -= 1
    elif lbl[n]+1 == x:
        
        ans += npl[n] + 1
        break
    elif lbl[n]+1 < x < 2*lbl[n]+2:
        
        x -= lbl[n]+2
        ans += npl[n]+1
    elif x == 2 + 2*lbl[n]:
        
        ans += 2*npl[n] + 1

print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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

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

ans = 0
for i in range(N, -1, -1):
    if i == 0 and X >= 1:
        ans += 1
        break

    if X <= 1:
        break
    elif X <= l[i - 1] + 1:
        X -= 1
        continue 
    elif X == l[i - 1] + 2:
        ans += 1
        X -= 2
    else:
        ans += p[i - 1] + 1
        X -= l[i - 1] + 2
print(ans)

Solution (Python):
N,X = map(int,input().split())
ans=0
f=0
for i in range(N,1,-1):
    center = 2*pow(2,i)-1
    
    if X>center:
        X-=center
        ans+=pow(2,i)
    elif X==center:
        ans+=pow(2,i)
        f=1
        break
    elif X<center:
        X-=1

if f==0:
    ans+="BQQQB"[:X].count("Q")
print(ans)

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

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

lst = [1]

for _ in range(1,N+1):
  lst.append(2*lst[-1]+1)

pw = 2**(N+1)-3
rlt = 0
i = N-1
while 1:
  if X == 1:
    print(rlt)
    exit()
  elif X < pw+2:
    X -= 1
    pw = (pw-3)//2
    if i > 0: 
      i -= 1
    elif i == 0:
      print(rlt+1)
      exit()
  elif X == pw+2:
    rlt += lst[i]+1
    print(rlt)
    exit()
  elif X < 2*pw+3:
    X -= pw + 2
    pw = (pw-3)//2
    if i > 0:
      rlt += lst[i]+1
      i -= 1
    elif i == 0:
      print(rlt+3)
      exit()
  elif X == 2*pw+3:
    rlt += 2*lst[i]+1
    print(rlt)
    exit()

Solution (Python):
n,x=map(int,input().split())
patty=[1]
barger=[1]
ans=0
for i in range(n):
  patty.append(2*patty[-1]+1)
  barger.append(2*barger[-1]+3)
i=n
while x>0:
  for _ in range(n):
    if x>=barger[i]:
      x-=barger[i]
      ans+=patty[i]
      if x>0:
        ans+=1
        x-=1
      break
    i-=1
    x-=1
print(ans)

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):
N, X = map(int, input().split(' '))

level2p = [1] * (N + 1)
level2pb = [1] * (N + 1)

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


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

    if x <= 1:
        return 0
    elif x <= 1 + level2pb[n - 1]:
        return dfs(n - 1, x - 1)
    elif x <= 1 + level2pb[n - 1] + 1:
        return level2p[n - 1] + 1
    elif x <= 1 + level2pb[n - 1] + 1 + level2pb[n - 1]:
        return level2p[n - 1] + 1 + dfs(n - 1, x - 1 - level2pb[n - 1] - 1)
    else:
        return level2p[n]


print(dfs(N, X))

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

p = [1]
pb = [1]
np = 0
nx = X

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


def dfs(level):
    global np, nx

    if nx == 0:
        return

    if nx >= pb[level]:
        nx -= pb[level]
        np += p[level]
        return

    nx -= 1
    if nx == 0:
        return

    dfs(level - 1)

    if nx == 0:
        return

    nx -= 1
    np += 1

    if nx == 0:
        return

    dfs(level - 1)

    if nx == 0:
        return

    nx -= 1


dfs(N)

print(np)

Solution (Python):


import copy
import random
import bisect 
import fractions 
import math
import sys
import collections
from decimal import Decimal 

mod = 10**9+7
sys.setrecursionlimit(mod) 

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, X = LI()

"""
Lv i のバーガーの厚みをa[i]
Lv i に含まれるパティの数をp[i]
とすると
a[0] = 1
a[i] = 2 * a[i-1] + 3
p[0] = 1
p[i] = 2 * p[i - 1] + 1

X = 1 f(N, X) = 0

1 < X <= 1 + a[i - 1]
一番したのバン

2 + a[i - 1] < X
一番したのバン　＋　
"""
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())
tp=0
for i in range(n):
    ct = (2**(n-i+2)-4)//2+1
    if x==0:break
    if i==n-1:tp+='bpppb'[:x].count('p')
    else:
        pn = 2**(n-i)-1
        if x<ct:x-=1
        elif x>=ct:
            tp+=pn+1
            if x==ct:break
            x-=ct
print(tp)

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 solve():
    n, x = map(int, input().split())
    l = [1]
    nu = [1]
    for i in range(n):
        l.append(l[-1] * 2 + 3)
        nu.append(nu[-1] * 2 + 1)

    def chris(a, b):
        if a == 0:
            return b
        elif b <= a:
            return 0
        hl = l[a]
        if b >= hl - a:
            return nu[a]
        elif hl // 2 + 1 <= b:
            return nu[a - 1] + 1 + chris(a - 1, b - (hl // 2 + 1))
        return chris(a - 1, b - 1)

    print(chris(n, x))


solve()

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

lev = N
cur = X-1
ps = 0
for i in range(N+1):
    if lev == 0:
        ps += 1
        break

    if cur == 0:
        break
    elif cur == sum(burger[lev-1])+1:
        ps += burger[lev-1][0]+1
        break
    elif cur == sum(burger[lev])-1:
        ps += 2*burger[lev-1][0] + 1
        break

    if cur < sum(burger[lev])/2:
        cur -= 1
        lev -= 1
    else:
        ps += burger[lev-1][0] + 1
        cur -= sum(burger[lev-1]) + 2
        lev -= 1
print(ps)

Solution (Python):
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, X = mi()
    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

        if 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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, X = MAP()

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

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

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

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

	if x-1 <= L[i-1]:
		return solve(i-1, x-1)
	else:
		return P[i-1] + 1 + solve(i-1, x-L[i-1]-2)

print(solve(N, X))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, X = MAP()

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

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

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

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

	if x-1 <= L[i-1]:
		return solve(i-1, x-1)
	else:
		return P[i-1] + 1 + solve(i-1, x-L[i-1]-2)

print(solve(N, X))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, X = MAP()

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

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

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


print(solve(N, X))

Solution (Python):

import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

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


    def f(i,y):
        if i == 0:
            return 1
        if y == 1:
            return 0
        if 1 < y <= 1 + a[i-1]:
            return f(i-1,y-1)
        if y == 2 + a[i-1]:
            return p[i-1] + 1
        if 2 + a[i-1] < y <= 2 + a[i-1]*2:
            return p[i-1] + 1 + f(i-1,y-(2+a[i-1]))
        else:
            return p[i-1] * 2 + 1

    print(f(N,X))

    



if __name__ == '__main__':
    main()

Solution (Python):
import sys

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

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

def f(A,B):  
    if A == 0 and B == 1:
        res = 1
    else:
        if B == 1:
            res = 0
        elif 2 <= B <= 2**(A+1)-2:
            res = f(A-1,B-1)
        elif B == 2**(A+1)-1:
            res = 2**A
        elif 2**(A+1) <= B <= 2**(A+2)-2:
            res = 2**A + f(A-1,B-2**(A+1)+1)
        else:
            res = 2**(A+1)-1
    return res

print(f(N,X))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, X = MAP()

p = [0]*(N+1) 
p[0] = 1
q = [0]*(N+1) 
q[0] = 1

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

ans = 0
i = N
while 0 < X:
	while 0 < X < q[i]:
		i -= 1
		X -= 1
	if 0 < X:
		X -= q[i]
		ans += p[i]
	if 0 < X:
		X -= 1
		ans += 1

print(ans)

Solution (Python):

def main():
    N, X = map(int, input().split())
    nums = [None] * (N+1)
    pnums = [None] * (N+1)
    nums[0] = 1
    pnums[0] = 1
    for i in range(N):
        nums[i+1] = nums[i]*2 + 3
        pnums[i+1] = pnums[i]*2 + 1
    
    ans = 0
    while N >= 0:
        if N == 0:
            print(ans+1)
            break
        if X == 1:
            print(ans)
            break
        elif X <= nums[N-1]+1:
            X -= 1
            N -= 1
        elif X == nums[N-1]+2:
            print(ans+pnums[N-1]+1)
            break
        elif X < nums[N]:
            X -= nums[N-1]+2
            ans += pnums[N-1]+1
            N -= 1
        else:
            print(ans+pnums[N])
            break
    

if __name__ == "__main__":
    main()

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

def burger(n):
    if n ==0:
        return "P"
    else:
        return "B" + burger(n-1) + "P" + burger(n-1) + "B"

def burger_size(n):
    return 4*pow(2,n) - 3

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

print(countP(N,X))

Solution (Python):
import collections
n,x = map(int, raw_input().split(' '))
x-=1
mem = {}
def compute(n):
	if n in mem:
		return mem[n]
	if n == 0:
		return (1,1)
	else:
		h,p = compute(n-1)
		return (2*h + 3, 2*p + 1) 	
def iot(n,x,r,h):
	if h[0] > x: return
	if n == 0:
		h[0] += 1
		r[0] += 1
		return
	h[0] += 1
	if h[0] > x: return
	
	if h[0] + compute(n-1)[0] <= x:
		hh,pp = compute(n-1)
		h[0] += hh
		r[0] += pp
	else:
		iot(n-1, x, r, h)
	if h[0] > x: return
	
	h[0] += 1
	r[0] += 1

	if h[0] > x: return
	
	if h[0] + compute(n-1)[0] <= x:
		hh,pp = compute(n-1)
		h[0] += hh
		r[0] += pp
	else:
		iot(n-1, x, r, h)
	
	
	if h[0] > x: return
	
	h[0] +=1		
r,h = [0],[0]
iot(n,x,r,h)
print r[0]

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(a[-1]//2 +1)

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

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

a, p = [1], [1]

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

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

print (f(n,x))

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



def f(N, X):
    if N == 0:
        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):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,X=mi()

    def solve(n,x):
        
        if n == 0: return 1
        c = 2**(n+2)-3
        half = c//2

        res = 0
        if x <= half:
            if x == 1:
                res += 0
            else:
                res += solve(n-1,x-1)
        elif x == half+1:
            res += 2**(n-1+1) - 1 + 1
        elif x < c:
            res += 2**(n-1+1) - 1 + 1 + solve(n-1,x-(half+1))
        else:
            assert x == c
            res += 2**(n+1)-1

        return res

    print(solve(N,X))



if __name__ == "__main__":
    main()

Solution (Python):






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

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

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

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

        if X <= 1:
            return 0

        elif X <= 1 + whole[N-1]:
            return rec(N-1, X-1)

        elif X <= 1 + whole[N-1] + 1:
            return p[N-1] + 1

        elif X <= 1 + whole[N-1] + 1 + whole[N-1]:
            return p[N-1] + 1 + rec(N-1, X-(1+whole[N-1]+1))

        else:
            return p[N-1] + 1 + p[N-1]

    ans = rec(N, X)

    return ans


print(main())

Solution (Python):


import sys
stdin = sys.stdin
from functools import lru_cache

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

@lru_cache(maxsize=2**52-3)
def f(n, x):
    if n == 0:
        return 1

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

def main():
    n, x = na()
    print(f(n, x))


if __name__ == "__main__":
    main()

Solution (Python):
def rec(N,X):
    if N==0:
        return 1
    if X==0:
        return 0
    if 1<=X and X<=a[N-1]:
        return rec(N-1,X-1)
    if X==a[N-1]+1:
        return p[N-1]+1
    if a[N-1]+1<X:
        return rec(N-1,X-a[N-1]-2)+p[N-1]+1

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

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

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(100000)

N, X = in_nn()

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

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


def count(L, X):

    if L == 0:
        return 1

    if X == 1:
        return 0

    ret = 0
    if X <= blen[L] // 2:
        ret += count(L - 1, X - 1)
    else:
        ret += pcount[L - 1] + 1
        if X > blen[L] // 2 + 1:
            X -= blen[L] // 2 + 1
            X = min(X, blen[L - 1])
            ret += count(L - 1, X)

    return ret


def main():

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


if __name__ == '__main__':
    main()

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


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

total_ls = [1]
pati_ls = [1]

for i in range(50):
    total_ls.append(3 + 2 * total_ls[-1])
    pati_ls.append(1 + 2 * pati_ls[-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 cnt_p(n, x):
    if n == 0:
        if x <= 0:
            return 0
        return 1
    elif x <= 1 + a[n - 1]:
        return cnt_p(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + cnt_p(n - 1, x - 2 - a[n - 1])


print(cnt_p(n, x))

Solution (Python):
def count_patties(L, x):
    if L == 0:
        return 0 if x <= 0 else 1
    if x <= total_layers[L - 1] + 1:
        return count_patties(L - 1, x - 1)
    else:
        return (
            count_patties(L - 1, x - total_layers[L - 1] - 2) + 1 + total_patties[L - 1]
        )


N, X = map(int, input().split())
total_layers = [2 ** (i + 2) - 3 for i in range(51)]
total_patties = [2 ** (i + 1) - 1 for i in range(51)]
print(count_patties(N, X))

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

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

print(f(N,X))

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


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

    a = pow(2, n + 1) - 3
    b = pow(2, n) - 1

    if x == 1:
        return 0
    elif x <= 1 + a:
        return func(n - 1, x - 1)
    elif x == 2 + a:
        return 1 + b
    elif x <= 2 * a + 2:
        return b + 1 + func(n - 1, x - 2 - a)
    else:
        return 2 * b + 1


print(func(N, X))

Solution (Python):
def solve(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif 1 < x < layer[n] // 2 + 1:
        return solve(n-1, x-1)
    elif x == layer[n] // 2 + 1:
        return patty[n-1] + 1
    elif layer[n] // 2 + 1 < x < layer[n]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return patty[n]


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

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

print(solve(N, X))

Solution (Python):
def solve(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif 1 < x <= 1 + layer[n-1]:
        return solve(n-1, x-1)
    elif x == 2 + layer[n-1]:
        return patty[n-1] + 1
    elif 2 + layer[n-1] < x <= 2 + 2 * layer[n-1]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return 2 * patty[n-1] + 1


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

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

print(solve(N, X))

Solution (Python):
def solve(n, x):
    if x == 1:
        return int(n <= 0)
    elif 1 < x <= 1 + layer[n-1]:
        return solve(n-1, x-1)
    elif x == 2 + layer[n-1]:
        return patty[n-1] + 1
    elif 2 + layer[n-1] < x <= 2 + 2 * layer[n-1]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return 2 * patty[n-1] + 1


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

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

print(solve(N, X))

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

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

Solution (Python):
n,x=map(int,input().split())
l=[1]
for i in range(50): l+=[l[-1]*2+3]
from functools import lru_cache
@lru_cache(None)
def f(n,x):
  return int(x>0) if n<1 else f(n-1,l[n-1])+1+f(n-1,x-l[n-1]-2) if x>l[n]//2 else f(n-1,x-1)
print(f(n,x))

Solution (Python):
n,x=map(int,input().split())
l=[1]
for i in range(50): l+=[l[-1]*2+3]
from functools import lru_cache
@lru_cache(None)
def f(n,x):
  if n<1: return int(x>0)
  if x<=l[n]//2: return f(n-1,x-1)
  return f(n-1,l[n-1])+1+f(n-1,x-l[n-1]-2)
print(f(n,x))

Solution (Python):
nn,xx=map(int,input().split())
def f(n,x):
  if x==0:
    return 0
  if n==0:
    return 1
  if x==2**(n+2)-3:
    return 2**(n+1)-1
  b=2**(n+1)-3
  u=min(b,max(0,x-2-b))
  l=min(x-1,b)
  return f(n-1,u)+(1 if x>b+1 else 0)+f(n-1,l)
print(f(nn,xx))

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 cnt(n,x):
	if n==0 and x<=0:
		return 0
	if n==0 and x>=1:
		return 1
	m=(B[n]+1)//2
	if x<m:
		return cnt(n-1,x-1)
	elif x==m:
		return P[n-1]+1
	elif x>m:
		return P[n-1]+1+cnt(n-1, x-m) 

print(cnt(n,x))

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

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

ans = 0


def f(x, i):
  global ans

  if x == An[i]:
    ans += Pn[i]
    print(ans)

  elif An[i]//2 + 1 < x < An[i]:
    ans += Pn[i-1] + 1
    f(x-(An[i]//2 + 1), i-1)

  elif An[i]//2 + 1 == x:
    ans += Pn[i-1] + 1
    print(ans)

  elif 1 < x <= An[i]//2:
    f(x-1, i-1)

  else:
    print(ans)

f(X, N)

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

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

Solution (Python):
def dfs(i,x):
 if i==0:return 1 if x>0else 0       
 if x<=1+l[i-1]:return dfs(i-1,x-1) 
 return 1+p[i-1]+dfs(i-1,x-2-l[i-1])
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)
print(dfs(n,x))

Solution (Python):
n , x = map(int, input().split())
l = 2**(n+2)-3

ans = 0
k=n
while l>=1:
    if x==(l+1)//2:
        ans+=2**(k)
        break
    if x==(l+1)//2-1:
        ans+=2**(k)-1
        break
    if x>(l+1)//2:
        ans+=2**(k)
        x-=(l+1)//2-1
    k-=1
    x-=1
    l=(l-1)//2-1
print(ans)