Problem:
 Score : 400 points    Problem Statement In some other world, today is Christmas.  Mr. Takaha decides to make a multi-dimensional burger in his party. A level- L burger ( L is an integer greater than or equal to 0 ) is the following thing:   A level- 0 burger is a patty.  A level- L burger (L \geq 1) is a bun, a level- (L-1) burger, a patty, another level- (L-1) burger and another bun, stacked vertically in this order from the bottom.   For example, a level- 1 burger and a level- 2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.  The burger Mr. Takaha will make is a level- N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?      Constraints  1 \leq N \leq 50  1 \leq X \leq ( the total number of layers in a level- N burger )  N and X are integers.         Input Input is given from Standard Input in the following format:  N  X       Output Print the number of patties in the bottom-most X layers from the bottom of a level- N burger.        Sample Input 1 2 7      Sample Output 1 4  There are 4 patties in the bottom-most 7 layers of a level- 2 burger ( BBPPPBPBPPPBB ).       Sample Input 2 1 1      Sample Output 2 0  The bottom-most layer of a level- 1 burger is a bun.       Sample Input 3 50 4321098765432109      Sample Output 3 2160549382716056  A level- 50 burger is rather thick, to the extent that the number of its layers does not fit into a 32 -bit integer.

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    global a, p
    N, X = LI()
    
    
    a, p = [1], [1]
    for i in range(N):
        a.append(a[i] * 2 + 3)
        p.append(p[i] * 2 + 1)
    print(make_burger(N, X))
    return


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


if __name__ == '__main__':
    main()

Solution (Python):
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,X=rl()

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

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


ans = 0

for i in range(N-1,-1,-1):
    if X==1:
        X -= 1
        break
    elif X <= 1+l[i]:
        X -= 1
        if i == 0:
            ans += 1
            break
    elif X == 1+l[i]+1:
        X -= 1+l[i]+1
        ans += p[i]+1
        break
    elif X <= 2+2*l[i]:
        X -= 2+l[i]
        ans += p[i]+1
        if i == 0:
            ans += 1
            break
    else:
        X -= 3+2*l[i]
        ans += 2*p[i]+1
        break
print(ans)

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

if x == 1:
    print(0)
    exit()

b = [0 for _ in range(n + 1)]
p = [0 for _ in range(n + 1)]

b[0] = 1
p[0] = 1

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

def burger(s, t):
    if t == 0:
        return 0
    if s == 0:
        return 1
    if t <= b[s - 1]:
        return burger(s - 1, t - 1)
    elif t == b[s - 1] + 1:
        return p[s - 1]
    elif t == b[s - 1] + 2:
        return p[s - 1] + 1
    else:
        return burger(s - 1, t - b[s - 1] - 2) + p[s - 1] + 1

print(burger(n, x))

Solution (Python):
bargarls = [0]*51;patyls = [0]*51
def bargar(n):
        global bargarls
        if n==1:
                bargarls[n-1] = 1
                return 1
        else:
                num = 2*bargar(n-1) + 3
                bargarls[n-1] = num
                return num
def paty(n):
        global patyls
        if n == 1:
                patyls[n-1] = 1
                return 1
        else:
                num = 2*paty(n-1) + 1
                patyls[n-1] = num
                return num
bargar(51)
paty(51)
def ans(n,x):
        global patyls 
        global bargarls
        if n >= x:return 0
        elif (bargarls[n]+1)//2 > x:return ans(n-1,x-1)
        elif (bargarls[n]+1)//2 == x:return (patyls[n]+1)//2
        elif bargarls[n] == x:return patyls[n]
        else:return (patyls[n]+1)//2 + ans(n-1,x-(bargarls[n]+1)//2)
n,x = map(int,input().split())
print(ans(n,x))

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

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

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

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


Patti = [1]  
Size = [1]   
for i in range(50):
    Patti.append(Patti[-1] * 2 + 1)
    Size.append(Size[-1] * 2 + 3)


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

    
    if 1 < x <= 1 + Size[n - 1]:
        return solve(n - 1, x - 1)

    
    if x == 1 + Size[n - 1] + 1:
        return Patti[n - 1] + 1

    
    if 1 + Size[n - 1] + 1 < x < Size[n]:
        return 1 + Patti[n - 1] + solve(n - 1, x - (1 + Size[n - 1] + 1))

    
    if x == Size[n]:
        return Patti[n]


print(solve(N, X))

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

hambs = [(1, 1)]
for l in range(1, n+1):
    n_p, n_l = hambs[l-1]
    hambs.append((2*n_p+1, 2*n_l+3))



def eat(m, y):
    if y == 0:
        return 0
    if m == 0:
        return 1

    if y < 2+hambs[m-1][1]:
        return eat(m-1, y-1)
    elif y == 2+hambs[m-1][1]:
        return hambs[m-1][0] + 1
    elif 2+hambs[m-1][1] < y and y < hambs[m][1]:
        return hambs[m-1][0] + 1 + eat(m-1, y-(2+hambs[m-1][1]))
    else:
        return hambs[m][0]
print(eat(n, x))

Solution (Python):



import sys
input = sys.stdin.readline

N, X = list(map(int, input().split()))
layers = [1]
patties = [1]
l = 1
p = 1
for _ in range(N):
    l = 2 * l + 3
    layers.append(l)
    p = 2 * p + 1
    patties.append(p)


def dfs(n, x):
    if n == 0:
        return patties[0]
    p = layers[n-1]
    if x == 1:
        return 0
    if x <= 1 + p:
        return dfs(n-1, x-1)
    if x == 1 + p + 1:
        return patties[n-1] + 1
    if x <= 1 + p + 1 + p:
        return patties[n-1] + 1 + dfs(n-1, x-(1+p+1))
    return patties[n]


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


if __name__ == '__main__':
    main()

Solution (Python):
import math














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


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


size, patty = [1], [1]
for i in range(N):
    size.append(size[i] * 2 + 3)
    patty.append(patty[i] * 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):
def count(n,x):
    n_1_element = 2**(n+1)-3
    if x == 0:
        return 0
    if n == 0:
        return 1
    if (x <= n_1_element+1):
        return count(n-1,x-1)
    else:
        return 2**n + count(n-1,x-n_1_element-2)

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

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

if a[-1][0] in (x,x-1):
  print(a[-1][1]);exit()

s=0
for k in range(3,len(a)*2+1):
  i,j = a[-k // 2]
  x -= k % 2
  if i <= x:
    x-=i;s+=j
    if x>=1:x-=1;s+=1

print(s)

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

if a[-1][0] in (x,x-1):
  print(a[-1][1])
  exit()
a=a[:-1]
s=0
for k in range(1,len(a)*2+1):
  i,j = a[-k // 2]
  x -= k % 2
  if i <= x:
    x-=i;s+=j
    if x>=1:
      x-=1;s+=1

print(s)

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

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

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



def bur(a,b):
    if a==0 :
        if b==0 :
            return 0
        else :
            return 1
    elif b<=1 :
        return 0
    elif b<=1+B[a-1][0] :
        return bur(a-1,b-1)
    elif b<=1+B[a-1][0]+1 :
        return B[a-1][1]+1
    elif b<=1+B[a-1][0]+1+B[a-1][0] :
        return B[a-1][1]+1+bur(a-1,b-2-B[a-1][0])
    elif b<=1+B[a-1][0]+1+B[a-1][0]+1 :
        return B[a-1][1]*2+1
    print(a)
    

print(bur(n,x))

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

Solution (Python):
def L(N):
    if N==0:
        return 1
    else:
        prev_L = L(N-1)
        return 1+prev_L+1+prev_L+1
def numP(N):
    if N==0:
        return 1
    else:
        prev_P = numP(N-1)
        return 2*prev_P+1
def eated_P(N,X):
    ans = 0
    fh=int(L(N)/2)
    if X<=0:
        return 0
    elif N==0:
        return 1
    elif fh<X:
        ans = numP(N-1)+1+eated_P(N-1,X-fh-1)
        return ans
    else:
        rem = X-1
        ans = eated_P(N-1,rem)
        return ans
N,X = map(int,input().split())
print(eated_P(N,X))

Solution (Python):






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





def p(n):
    return 2 ** (n+1) - 1
def b(n):
    return 2 ** (n+1) - 2
def l(n):
    return 2 ** (n+2) - 3





def func(i, x):
    if x == 0:
        return 0
    elif x <= l(i-1) + 1:
        return func(i-1, x-1)
    elif x == l(i-1) + 2:
        return p(i-1) + 1
    elif x <= 2 * l(i-1) + 2:
        return p(i-1) + 1 + func(i-1, x - l(i-1) - 2)
    else:
        return 2 * p(i-1) + 1





print(func(n,x))

Solution (Python):
N,X=map(int,input().split())
Length=[1]
for i in range(1,51):
    Length.append(Length[i-1]*2+3)
def DP(N,point):
    if N == 0:
        return 1
    if point==1:
        return 0
    if 2<=point<=Length[N]//2:
        return DP(N-1,point-1)
    if point==Length[N]//2+1:
        return DP(N-1,point-2)+1
    if Length[N]//2+2<=point and\
            point <=Length[N]-1:
        return DP(N-1,point-Length[N-1]-2)+\
                DP(N-1,Length[N-1])+1
    if point==Length[N]:
        return DP(N-1,Length[N-1])*2+1
print(DP(N,X))

Solution (Python):


from sys import stdin

input = stdin.readline

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

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

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

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

print(f(N,X))

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

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

def rec(x, n, tmp):
    if n == 0:
        return tmp + 1
    m = fac(n)
    if x == 0:
        return tmp + 0
    elif x == m-1:
        return tmp + (m+1)//2
    elif x == (m-1)//2:
        return tmp + (m+3)//4
    elif 0 < x < (m-1)//2:
        return rec(x-1, n-1, tmp)
    else:
        return rec(x-(m+1)//2, n-1, tmp+(m+3)//4)

print(rec(X-1, N, 0))

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

if __name__=="__main__":
  n, x = input().split()
  a = [1]
  p = [1]
  for i in range(0, int(n)):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
  print(md_burger(int(n), int(x)))

Solution (Python):
n, x = map(int, input().split())
def layer(n):
    return 2 ** (n+2) - 3
def full(n):
    return 2 ** (n+1) - 2
def solve(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 0
    if x >= layer(n):
        return full(n)
    if x <= layer(n-1) + 1:
        return 1 + solve(n-1, x-1)
    else:
        return full(n-1) + solve(n-1, x - layer(n-1) - 2) + 1
print(x - solve(n,x))

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

L = n
res = 0
while(1):
    if(L == 0):
        if(k==(n+1)):
            res += 1
        break
    bar = (n-L) + (((1<<(L+2))-3)>>1) + 1

    if k < bar:
        L -= 1  
    elif k == bar:
        res += (1<<L)
        break 
    else:
        res += (1<<L)
        
        k -= ((1<<(L+1)) -2)
        if(k == bar):
            k -= 1
        L -= 1
print(res)

Solution (Python):


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

l = [1]
p = [1]

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


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


print(f(N, X))

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


def count(N, X):
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif 1 < X < 2**(N+1) - 1:
        return count(N-1, X-1)
    elif X == 2**(N+1) - 1:
        return 2**N
    elif 2**(N+1) - 1 < X:
        return 2**N + count(N-1, X-2**(N+1)+1)


print(count(N, X))

Solution (Python):
from functools import lru_cache

@lru_cache()
def eat(n, x):  
    
    if n == 0:
        if x == 1:
            return 1  
    if x == 1:
        return 0  
    elif x <= 1 + thickness[n - 1]:
        return eat(n - 1, x - 1)
    elif x <= 1 + thickness[n - 1] + 1:
        return patties[n - 1] + 1
    elif x <= 1 + thickness[n - 1] + 1 + thickness[n-1]:
        return patties[n - 1] + 1 + eat(n - 1, x - 1 - thickness[n-1] - 1)
    else:
        return patties[n - 1] + 1 + patties[n - 1]

    return 0

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

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

print(eat(N,X))

Solution (Python):
from functools import lru_cache

@lru_cache()
def eat(n, x):  
    
    if n == 0:
        if x == 1:
            return 1  
    if x == 1:
        return 0  
    elif x <= 1 + thickness[n - 1]:
        return eat(n - 1, x - 1)
    elif x <= 1 + thickness[n - 1] + 1:
        return patties[n - 1] + 1
    elif x <= 1 + thickness[n - 1] + 1 + thickness[n-1]:
        return patties[n - 1] + 1 + eat(n - 1, x - 1 - thickness[n-1] - 1)
    else:
        return patties[n - 1] + 1 + patties[n - 1]

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

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

print(eat(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 a(N):
    if N == 0:
        return 1
    else:
        return a(N-1)*2 + 3


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


def judge(N, X, an, pn, tp):
    
    sn = an
    sl = int((an - 3) / 2)
    pl = int((pn - 1) / 2)
    
    
    
    
    
    if X == 1:
        
        if N == 0:
            return tp + 1
        else:
            return tp + 0
    elif (X > 1) & (X < sl+1):
        
        return judge(N-1, X-1, sl, pl, tp)
    elif (X == sl + 1) | (X == sl + 2):
        
        if X == sl + 1:
            tp = pl + tp
            return tp
        else:
            tp = pl + 1 + tp
            return tp
    elif (X > sl + 2) & (X < sn):
        
        tp = pl + 1 + tp
        return judge(N-1, X-sl-2, sl, pl, tp)
    elif X == sn:
        
        return tp + pn


N, X = map(int, input().split())
an = a(N)
pn = p(N)
tp = 0
result = judge(N, X, an, pn, tp)


print(result)

Solution (Python):
def calc_n_layers(n):
    memo = {}
    def calc(n):
        if n in memo:
            return memo[n]
        if n <= 0:
            return 1
        ret = 3 + calc_n_layers(n-1)*2
        memo[n] = ret
        return ret
    return calc(n)


def n_patties(n):
    memo = {}
    def calc(n):
        if n in memo:
            return memo[n]
        if n <= 0:
            return 1
        ret = n_patties(n-1)*2 + 1
        memo[n] = ret
        return ret
    return calc(n)


def solve(n, x):
    if x <= 0:
        return 0
    if n <= 0:
        return 1
    l = calc_n_layers(n)
    l2 = (l - 3) // 2
    if x-1 <= l2:
        return solve(n-1, x-1)
    else:
        x = x - 1
        ret = n_patties(n-1)
        x = x - l2
        ret += 1
        x = x - 1
        ret += solve(n-1, x)
        return ret


def main():
    N, X = list(map(int, input().split(' ')))
    print(solve(N, X))

if __name__ == '__main__':
    main()

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

len_l = [0] * 51
plen_l = [0] * 51


len_l[0] = 1
plen_l[0] = 1
for i in range(50):
    len_l[i + 1] = 2 * len_l[i] + 3
    plen_l[i + 1] = 2 * plen_l[i] + 1

def p_num(l, x):
    if l == 0:
        return 0 if x <= 0 else 1
    elif x <= len_l[l-1] + 1:
        return p_num(l - 1, x - 1)
    elif x == len_l[l-1] + 2:
        return plen_l[l-1] + 1
    else:
        return plen_l[l-1] + 1 + p_num(l - 1, x - len_l[l-1] - 2)

print(p_num(N, X))

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

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

def p_eat(N,X):
  if X == 0:
    return 0
  elif X == bn[N]:
    return pn[N]
  elif bn[N-1]+1 < X:
    return pn[N-1]+1+p_eat(N-1, X-bn[N-1]-2)
  else:
    return p_eat(N-1, X-1)

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

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


def countPatty(N, X):
    if N == 0:
        return 1 if X >= 1 else 0
    elif X <= 1:
        return 0
    elif 1 < X <= L[N - 1] + 1:
        return countPatty(N - 1, X - 1)
    elif L[N - 1] + 1 < X:
        return P[N - 1] + 1 + countPatty(N - 1, X - (L[N - 1] + 2))


print(countPatty(N, X))

Solution (Python):
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n):
    if n<1:return 1
    return b(n-1)*2+3
@lru_cache(maxsize=None)
def p(n):
    if n<1:return 1
    return p(n-1)*2+1
def solve(n,x):
    if n<1:return int(x>0)
    if x-2<b(n-1):return(solve(n-1,x-1))
    return p(n-1)+solve(n-1,x-b(n-1)-2)+1
print(solve(*map(int,input().split())))

Solution (Python):
from functools import lru_cache
@lru_cache(maxsize=None)
def b(n):
    if n<1:return 1
    return b(n-1)*2+3
@lru_cache(maxsize=None)
def p(n):
    if n<1:return 1
    return p(n-1)*2+1
def solve(n,x):
    if n<1:return int(x>0)
    if x-2<b(n-1):return(solve(n-1,x-1))
    return p(n-1)+solve(n-1,x-b(n-1)-2)+1
print(solve(*map(int,input().split())))

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

def p(n,x):
    if x<=n:
        return 0
    if n==0:
        return 1
    i=0
    while 2**(2+i)-3+n-i<=x:
        i+=1
    if 2**(i+1)-2+n-i==x:
        return 2**i-1
    else:
        return 2**i+p(i-1,x-(2**(i+1)+n-i-2)-1)

print(p(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-a[n-1]-2)

print(f(n,x))

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

Solution (Python):
import sys

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

def main():
  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)

  ans = f(N, X, a, p)
  print(ans)


if __name__ == '__main__':
  main()

Solution (Python):
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]
dy8, dx8 = [0, -1, 0, 1, 1, -1, -1, 1], [1, 0, -1, 0, 1, 1, -1, -1]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def ceil(a, b):
    return (a + b - 1) // b



def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)



def lcm(a, b):
    g = gcd(a, b)
    return a / g * b


def check(N, X):
    s = "P"
    for i in range(N):
        s = "B" + s + "P" + s + "B"
    return s[:X].count("P")


def func(N, X, P, B):
    if X == 0:
        return 0
    if N == 0:
        return 1

    num = P[N - 1] + B[N - 1]

    ans = 0
    X -= 1
    if X >= num:
        ans += P[N - 1]
        X -= num
    else:
        return func(N - 1, X, P, B)

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

    if X >= num:
        X -= num
        ans += P[N - 1]
    else:
        return ans + func(N - 1, X, P, B)

    X -= 1

    return ans


def solve(N, X):
    P = [0] * 51
    B = [0] * 51
    P[0] = 1
    for i in range(1, 51):
        P[i] = P[i - 1] * 2 + 1
        B[i] = B[i - 1] * 2 + 2

    return func(N, X, P, B)


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


if __name__ == '__main__':
    main()

Solution (Python):



P = True
B = False
lenP = lambda x: 2*x + 1
lenB = lambda x: 2*x + 2
lenS = lambda x: 2*x + 3

def main():
  n, x = map(int, input().split())
  _next = lambda burger: [B] + burger + [P] + burger + [B]
  burger = [P]
  Pn = {0:1}
  Bn = {0:0}
  Sn = {0:1}
  for i in range(n):
    Pn[i+1] = lenP(Pn[i])
    Bn[i+1] = lenB(Bn[i])
    Sn[i+1] = lenS(Sn[i])
  _sum = 0
  middle = int((Sn[n] + 1)/2)
  for i in list(range(1, n+1))[::-1]:
    if middle == x:
      _sum += int(Pn[i-1])
      break
    elif middle < x:
      _sum += Pn[i-1] + 1
      middle += int((Sn[i-1]+1)/2)
    else:
      middle -= int((Sn[i-1]+1)/2)
      pass
  if middle <= x:
    _sum += 1

  print(_sum)

  pass

if __name__=='__main__':
  main()

Solution (Python):
n, x = [int(i) for i in input().split()]

a = [1]
p = [1]

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

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

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

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

patty = [0]*(n+1)
length = [0]*(n+1)
for L in range(n+1):
    if L==0:
        patty[L] = 1
        length[L] = 1
    else:
        patty[L] = patty[L-1]*2+1
        length[L] = length[L-1]*2+3

def patty_n(L,X): 
    
    if X==0:
        return 0
    elif L==0:
        return 1
    else:
        l = length[L-1]
        if X==1:
            return 0
        elif 1<X<=1+l:
            return patty_n(L-1, X-1)
        else:
            return patty[L-1]+1+patty_n(L-1, X-l-2)

print(patty_n(n,x))

Solution (Python):

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













def burgar(L):
    if L==0:
        return 'P'
    else:
        tmp = burgar(L-1)
        return 'B'+tmp+'P'+tmp+'B'

patty = [0]*(n+1)
length = [0]*(n+1)
for L in range(n+1):
    if L==0:
        patty[L] = 1
        length[L] = 1
    else:
        patty[L] = patty[L-1]*2+1
        length[L] = length[L-1]*2+3

def patty_n(L,X): 
    
    if X==0:
        return 0
    elif L==0:
        return 1
    else:
        l = length[L-1]
        
        if X==1:
            return 0
        elif 1<X<=1+l:
            return patty_n(L-1, X-1)
        else:
            return patty[L-1]+1+patty_n(L-1, X-l-2)


print(patty_n(n,x))

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



def Ber(L):
    if L == 0:
        return 1
    return 2*Ber(L-1) + 3



def Patty(L):
    if L == 0:
        return 1
    return 2*Patty(L-1) + 1

def rec(L=N,bottom=X):
    if L == 0:
        return 1
    if bottom <= 1:
        return 0
    elif bottom <= 1 + Ber(L-1):
        return rec(L-1,bottom-1)
    elif bottom == 1 + Ber(L-1) + 1:
        return Patty(L-1) + 1
    elif bottom <= 1 + Ber(L-1) + 1 + Ber(L-1):
        return Patty(L-1) + 1 + rec(L-1,bottom-(1+Ber(L-1)+1))
    elif bottom <= 1 + Ber(L-1) + 1 + Ber(L-1) + 1:
        return Patty(L-1) + 1 + Patty(L-1)

print(rec())

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



def Ber_memo(L,memo=[0]*(N+1)):
    if L == 0:
        return 1
    if memo[L] != 0:
        return memo[L]
    memo[L] = 2*Ber_memo(L-1) + 3
    return memo[L]



def Patty_memo(L,memo=[0]*(N+1)):
    if L == 0:
        return 1
    if memo[L] != 0:
        return memo[L]
    memo[L] = 2*Patty_memo(L-1) + 1
    return memo[L]

def rec_memo(L=N,bottom=X):
    if L == 0:
        return 1
    if bottom <= 1:
        return 0
    elif bottom <= 1 + Ber_memo(L-1):
        return rec_memo(L-1,bottom-1)
    elif bottom == 1 + Ber_memo(L-1) + 1:
        return Patty_memo(L-1) + 1
    elif bottom <= 1 + Ber_memo(L-1) + 1 + Ber_memo(L-1):
        return Patty_memo(L-1) + 1 + rec_memo(L-1,bottom-(1+Ber_memo(L-1)+1))
    elif bottom <= 1 + Ber_memo(L-1) + 1 + Ber_memo(L-1) + 1:
        return Patty_memo(L-1) + 1 + Patty_memo(L-1)

print(rec_memo())

Solution (Python):
def eat(x,n):
    ans,p = 0,0
    while(n>=0 and x>0):
        p = 2**(n+1)-1
        if x>=p:
            x-=p
            ans+=int((p+1)/2)
        else:
            x-=1
        n-=1
    return ans

if __name__ == '__main__':
    n,x=map(int, input().split())
    p = 2**(n+1)-1
    if x<n:
        print(0)
    elif x>=2*p-n-1:
        print(p)
    else:
        print(int(eat(x,n)))

Solution (Python):
def f(k,x):
    if(k==0):
        return 1
    assert(x>=1)
    if(x==1):
        return 0
    if(x<l[k-1]+2):
        return f(k-1, x-1)
    elif(x==l[k-1]+2):
        return b[k-1] + 1
    else:
        return b[k-1] + 1 + f(k-1, x-2-l[k-1])

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

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

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


def dfs(n, x):
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif 1 < x and x <= 1+na[n-1]:
        return dfs(n-1, x-1)
    elif 2+na[n-1] == x:
        return np[n-1]+1
    elif 2+na[n-1] < x and x <= 2+2*na[n-1]:
        return np[n-1]+1+dfs(n-1, x-2-na[n-1])
    elif x == 3+2*na[n-1]:
        return 2*np[n-1]+1

na = [1]
np = [1]
for i in range(N):
    na.append(na[-1]*2+3)
    np.append(np[-1]*2+1)
print(dfs(N, X))

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

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