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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
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

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

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

print(solve(N, X))

Solution (Python):
def f(n):
    if n==0:
        return 1
    return 2*f(n-1)+3
def g(n):
    if n==0:
        return 1
    return 2*g(n-1)+1
def F(n,x):
    if n==0:return 1
    if x<=n:return 0
    if x<=f(n-1)+1:
        return F(n-1,x-1)
    elif x==f(n-1)+2:
        return g(n-1)+1
    else:
        return g(n-1)+1+F(n-1,x-f(n-1)-2)
N,X = map(int,input().split())
print(F(N,X))

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n, x = [int(x) for x in input().split()]

total = [1]
p = [1]

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

ans = 0



def solve(x, i):
    global ans
    if x == 0:
        ans += 1
        return
    if i <= 1 + total[x - 1]:
        if i - 1 > 0:
            solve(x - 1, i - 1)
    else:
        ans += 1 + p[x - 1]
        if i - (2 + total[x - 1]) > 0:
            solve(x - 1, i - (2 + total[x - 1]))

solve(n, x)
print(ans)

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

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

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

print(func(x, n))

Solution (Python):
from functools import lru_cache

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

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

@lru_cache(maxsize=None)
def calc(level, N):
    if level == 0:
        return 1 if N > 0 else 0

    N = min(N, size(level))

    ret = 0
    N -= 1

    if N >= size(level - 1):
        ret += calc(level - 1, size(level - 1))
        N -= size(level - 1)

        if N >= 1:
            ret += 1
            N -= 1

    return ret + calc(level - 1, N)

print(calc(N, X))

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

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

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

Solution (Python):
level, num_eat = map(int,input().split())

def get_layers(level):
    return 2**(level+2) - 3

def get_patty(level):
    return 2**(level+1) - 1

def f(level, x):
    if level == 0:
        return 1
    elif x == 1:
        return 0
    elif 1 < x <= 1 + get_layers(level-1):
        return f(level-1, x-1)
    elif x == 2 + get_layers(level-1):
        return get_patty(level - 1) + 1
    elif 2 + get_layers(level-1) < x <= 2 + 2 * get_layers(level-1):
        return get_patty(level-1) + 1 + f(level-1,x-2-get_layers(level-1))
    elif x == 3 + 2*get_layers(level-1):
        return 2*get_patty(level - 1) + 1

print(f(level, num_eat))

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

def solve(n,x):
    total=[1]
    paty=[1]
    for i in range(50):
        total.append(total[i]*2+3)
        paty.append(paty[i]*2+1)

    @lru_cache(maxsize=None)
    def f(N,X):
        if N==0 and X<=0:
            return 0
        elif N==0 and X>0:
            return 1
        elif X<=total[N-1]+1:
            return f(N-1, X-1)
        else:
            return paty[N-1]+1+f(N-1, X-total[N-1]-2)
    return print(f(n,x))

if __name__=='__main__':
    n,x=map(int,input().split())
    solve(n,x)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n,x=map(int, input().split())

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

def rec(N, X): 
    if N==0 and X<=0:
        return 0 
    elif N==0 and X>0:
        return 1
    elif X<=1+total[N-1]:
        return rec(N-1, X-1)
    else:
        return paty[N-1] + 1 + rec(N-1, X-2-total[N-1])

print(rec(n, x))

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

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

print(f(n,x))

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

def count_p(n, x):
  if x == 0:
    return 0
  elif n == 0:
    return 1
  elif x > 2**(n+1)-2:
    return 2**(n)-1 + 1 + count_p(n-1, min(x-(2**(n+1)-1), 2**(n+1)-3))
  else:
    return count_p(n-1, x-1)
  
print(count_p(n,x))

Solution (Python):
N, X = 2, 7

N, X = 50, 4321098765432109

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


def calculate(n, x):
    p = 1
    level = 0
    dialations = [1]

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

    
    

    res = calculate2(level, dialations, x - 1)
    print(res)


def calculate2(currentLevel, dialations, x):
    keyPoint0 = 0
    keyPoint1 = keyPoint0 + dialations[currentLevel - 1] + 1

    if currentLevel == 0:
        return 1

    if x == -1:
        return 2 * calculate2(currentLevel - 1, dialations, -1) + 1

    if x == keyPoint0:
        return 0

    if (x > keyPoint0) and (x < keyPoint1):
        return calculate2(currentLevel - 1, dialations, x - 1)

    if x == keyPoint1:
        return calculate2(currentLevel - 1, dialations, -1) + 1

    if (x > keyPoint1):
        return calculate2(currentLevel - 1, dialations, -1) + 1 + calculate2(currentLevel - 1, dialations,
                                                                             x - dialations[currentLevel - 1] - 2)


calculate(N, X)

Solution (Python):
n, x = map(int, input().split())
def solve(n, i):
    if n==0:
        return 1
    if i==0:
        return 0
    if i<(2**(n+2)-3)//2:
        return solve(n-1, i-1)
    if i==(2**(n+2)-3)//2:
        return 2**n
    if i<2**(n+2)-4:
        return 2**n + solve(n-1, i-(2**(n+2)-3)//2-1)
    return 2**(n+1) - 1
print(solve(n, x-1))

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

arr=[1]*(n+1)
patty=[1]*(n+1)
for i in range(n):
    arr[i+1]=3+2*arr[i]
    patty[i+1]=1+2*patty[i]

def f(n,x):
    
    if n==0:
        return 1
    elif x==1:
        return 0
    elif x==arr[n] or x==arr[n]-1:
        return patty[n]
    elif x<arr[n]//2+1:
        return f(n-1,x-1)
    elif x==arr[n]//2+1:
        return patty[n-1]+1
    else:
        return patty[n]-f(n-1,arr[n]-x-1)

print(f(n,x))

Solution (Python):

import sys
input = sys.stdin.readline




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




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




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

print(dfs(N,X))

Solution (Python):
pa = [1]
atu = [1]

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

Solution (Python):
import sys


import math
import collections

import bisect
import itertools
import fractions

import copy
import heapq
import decimal

import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





def main():
    n, x = ns()
    lim = 51
    total = [int(0) for _ in range(lim)]
    P_total = [int(0) for _ in range(lim)]

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

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

    ans = 0
    base = 1
    L = n
    flg = True
    while base != x and L != 0:
        if base + total[L] // 2 <= x and flg:
            base += total[L] // 2
            ans += P_total[L - 1] + 1
            flg = False
        else:
            flg = True
            base += 1
            L -= 1
            if L == 0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

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

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


print(fx(N, X))

Solution (Python):
def calc(n,x):
  if x==1:
    if n==0:
      ans=1
    else:
      ans=0
  elif 1 < x < (num[n]+1)//2:
    ans= calc(n-1,x-1)
  elif x== (num[n]+1)//2:
    ans= pat[n-1]+1
  elif (num[n]+1)//2 < x <num[n]:
    ans= pat[n-1]+1+ calc(n-1, x- (num[n]+1)//2)
  else:   
    ans= pat[n]
  return ans


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

print(calc(N,X))

Solution (Python):
n,x = map(int,input().split())
cnt = 0
while n > 0 and x > 0:
    if x >= 2**(n+1)-1:
        cnt += 2**n
        x -= (2**(n+1)-1)
    else:
        x -= 1
    n -= 1
if x >= 1:
    cnt += 1
print(cnt)

Solution (Python):
def fn(k):
    return pow(2, k + 2) - 3

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

    sum_f = fn(n - 1)
    if x <= sum_f + 1:
        rec += pn(n - 1, x - 1)

    elif x == sum_f + 2:
        rec += pow(2, n)

    else:
        rec += pow(2, n) + pn(n - 1, x - (sum_f + 2))

    return rec

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

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


def saiki(n, x):
    
    if n == 5:
        if x == 1:
            return 0
        elif x <= 4:
            return x-1
        else:
            return 3

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


maisu = 1
for i in range(N):
    maisu = 2 * maisu + 3

ans = saiki(maisu, X)

print(ans)

Solution (Python):
N,X=list(map(int,input().split()))
p=[]
a=[]
def search(N):
    if N==0:
        p.append(1)
        a.append(1)
        return 1,1
    else:
        search(N-1)
        p.append(2*p[N-1]+1)
        a.append(2*a[N-1]+3)
search(N)
def bug(N,X):
    if N==0 and X>=1:return 1
    if X==1:return 0
    if 1<X<=1+a[N-1]:
        return bug(N-1,X-1)
    elif X==a[N-1]+2:
        return p[N-1]+1
    elif a[N-1]+2<X<=2+2*a[N-1]:
        return p[N-1]+1+bug(N-1,X-2-a[N-1])
    elif X==3+2*a[N-1]:
        return 2*p[N-1]+1
print(bug(N,X))

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

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

ans = rec(n, x, a, p)
print(ans)

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

for i in range(51):
    Size.append(Size[-1] * 2 + 3)
    Patty.append(Patty[-1] * 2 + 1)


def count_p(n, x):
    if x == 0:
        return 0
    if n == 0:
        return min(x, 1)
    if (Size[n]+1) // 2 > x:
        return count_p(n-1, x-1)
    elif (Size[n]+1) // 2 == x:
        return Patty[n-1] + 1
    else:
        return Patty[n-1] + 1 + count_p(n-1, x - ((Size[n]+1) // 2))


print(count_p(N, X))

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


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

    def rec(N, X):
        if X == 1 and N == 0:
            return 1
        elif X == 1 and N != 0:
            return 0
        elif 2 <= X <= 1+a[N-1]:
            return rec(N-1, X-1)
        elif X == 2+a[N-1]:
            return p[N-1]+1
        elif 3+a[N-1] <= X <= 2+a[N-1]*2:
            return p[N-1]+rec(N-1, X-a[N-1]-2)+1
        else:
            return p[N-1]*2+1
    print(rec(N, X))


resolve()

Solution (Python):
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


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

    @lru_cache(maxsize=None)
    def func(n, x):
        if n == 0:
            if x <= 0: return 0
            if x >= 1: return 1
        if x >= 2 ** (n + 2) - 3:
            return func(n - 1, x) * 2 + 1
        if x >= 2 ** (n + 1) - 1:
            return func(n - 1, x) + 1 + func(n - 1, x - (2 ** (n + 1) - 1))
        if x >= 1:
            return func(n - 1, x - 1)
        return 0

    print(func(N, X))




if __name__ == "__main__":
    main()

Solution (Python):
def dfs(N):
    if N == 0:
        return 1
    component = dfs(N-1)
    tower = 2 * component + 1 
    return tower

N, X = map(int, input().split())
ans = 0
while X > 0:
    for n in range(0, N+1):
        if X < 2**(n+3) - 3 + (N-(n+1)):
            if X > 2**(n+2) - 3 + (N-n):
                ans += dfs(n) + 1 
                X -= 2**(n+2) - 3 + (N-n) + 1
                N = n
            else:
                if n == 0 and X <= N:
                    X = 0
                else:
                    ans += dfs(n)
                    X -= 2**(n+2) - 3 + (N-n)
                    N = n
            break

print(ans)

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

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

hambargers = [1]
patties = [1]

for i in range(1, n+1):
    num = hambargers[i-1] * 2 + 3
    patty_num = patties[i-1] * 2 + 1
    hambargers.append(num)
    patties.append(patty_num)

def cal(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + hambargers[N-1]:
        return cal(N-1, X-1)
    else:
        return patties[N-1] + 1 + cal(N-1, X-2-hambargers[N-1])

print(cal(n, x))

Solution (Python):

import sys
sys.setrecursionlimit(10**7)

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

burger = [[0, 0] for _ in range(N)]
burger[0] = [1, 1]

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

ans = 0
while True:
    if N == 0:
        if X > 0:
            ans += 1
        break
    if X > burger[N-1][0]+2:
        ans += burger[N-1][1] + 1
        X -= burger[N-1][0]+2
        N -= 1
    elif X == burger[N-1][0]+2:
        ans += burger[N-1][1] + 1
        break
    elif X < burger[N-1][0]+2:
        X -= 1
        N -= 1
print(ans)

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

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




ans = 0
lv = n
tmp =x
while lv >= 0:
    z = (a[lv]-1)//2
    
    if lv == 0:
        if tmp >= 1:
            ans += 1
        break
    if tmp > z:
        ans += p[lv - 1] + 1
        tmp = tmp - z - 1
        lv -= 1
    elif tmp == z:
        ans += p[lv - 1]
        break
    else:
        tmp -= 1
        lv -= 1
        
    
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

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

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


def count_patties(l, x):
    
    if l == 0 and x == 1:
        return 1
    
    if x <= 1:
        return 0
    y = layers[l - 1]
    
    
    
    if x <= y + 1:
        
        return count_patties(l-1, max(x - 1, 0))
    else:
        
        return count_patties(l-1, min(x-y-2, y)) + patties[l-1] + 1

N, X = getNM()
print(count_patties(N, X))

Solution (Python):

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

a,x=MI()
size=[0 for i in range(a+1)]
size[0]=1
for i in range(a):
    size[i+1]=size[i]*2+3


patty=[0 for i in range(a+1)]
patty[0]=1
for i in range(a):
    patty[i+1]=2*patty[i]+1

def porb(k,n):
    if k==1 and n==0:
        return 1
    elif k==1:
        return 0
    elif k==size[n]:
        return patty[n]
    elif k>(size[n]+1)//2:
        return patty[n-1]+1+porb(k-(size[n]+1)//2,n-1)
    elif k==(size[n]+1)//2:
        return patty[n-1]+1
    else:
        return porb(k-1,n-1)

print(porb(x,a))

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def main():
    N, X = (int(_) for _ in input().split())

    ex2 = []
    num = 1
    for i in range(51):
        ex2.append(num)
        num *= 2

    def Height(L):
        return 4 * ex2[L] - 3

    def TotalPatty(L):
        return 2 * ex2[L] - 1

    def NumPatty(L, x):
        M = Height(L)
        m = (M+1)//2
        if x == 1:
            if L == 0: return 1
            else: return 0
        elif x == m: return TotalPatty(L-1) + 1
        elif x == M: return 2*TotalPatty(L-1) + 1
        elif 1 < x < m: return NumPatty(L-1, x-1)
        else: return TotalPatty(L-1) + 1 + NumPatty(L-1, x-(Height(L-1)+2))

    print(NumPatty(N, X))
    return

if __name__ == '__main__':
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18


n, x = Is()
Blen = [0]*(n+1)
P = [0]*(n+1)
Blen[0] = 1
P[0] = 1
for i in range(1, n):
    Blen[i] = Blen[i-1]*2 + 3
    P[i] = P[i-1]*2 + 1
def burger(i, y):
    if i == 0:
        return 0 if y <= 0 else 1
    if y <= Blen[i-1] + 1:
        return burger(i-1, y-1)
    else:
        return P[i-1] + 1 + burger(i-1, y-Blen[i-1]-2)
print(burger(n, x))

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

layer_size = [1]
P_cnt = [1]

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

  
  P_cnt.append(P_cnt[-1]*2+1)


def solve(level, x):
  if x == 1:
    return 0 if level > 0 else 1
  l = layer_size[level-1]
  p = P_cnt[level-1]
  if x <= 1+l:
    return solve(level-1, x-1)
  elif x == l+2:
    return p+1
  elif x <= 2*l+2:
    return p+1+solve(level-1, x-l-2)
  else:
    return 2*p+1
  
ans = solve(N, X)
print(ans)

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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)
    return 1+P[n-1]+f(n-1,x-A[n-1]-2)
def main():
    n,x=map(int,input().split())
    global A,P
    A=[1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645, 4294967293, 8589934589, 17179869181, 34359738365, 68719476733, 137438953469, 274877906941, 549755813885, 1099511627773, 2199023255549, 4398046511101, 8796093022205, 17592186044413, 35184372088829, 70368744177661, 140737488355325, 281474976710653, 562949953421309, 1125899906842621, 2251799813685245, 4503599627370493]
    P=[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247]
    print(f(n,x))

if __name__=='__main__':
    main()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
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)
    return 1+P[n-1]+f(n-1,x-A[n-1]-2)
def main():
    n,x=map(int,input().split())
    global A,P
    A=[1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645, 4294967293, 8589934589, 17179869181, 34359738365, 68719476733, 137438953469, 274877906941, 549755813885, 1099511627773, 2199023255549, 4398046511101, 8796093022205, 17592186044413, 35184372088829, 70368744177661, 140737488355325, 281474976710653, 562949953421309, 1125899906842621, 2251799813685245, 4503599627370493]
    P=[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247]
    print(f(n,x))

if __name__=='__main__':
    main()

Solution (Python):
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline

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

def S(n):
    return 2**(n+2)-3
def P(n):
    return 2**(n+1)-1

def count(n,x):
    if n == 0:
        return P(0)
    else:
        if x == 1:
            return 0
        if 1 < x <= S(n-1)+1:
            return count(n-1,x-1) 
        if x == S(n-1)+2:
            return 1 + count(n-1,x-2)
        if S(n-1)+2 < x <= 2*S(n-1)+2:
            return P(n-1) + 1 + count(n-1,x-2-S(n-1))
        else:
            return P(n-1) + 1 + count(n-1,x-3-S(n-1))

print(count(N,X))

Solution (Python):


import sys






















def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, x = mi()

    def calc_patty(level, num):
        '''
        level バーガーを下から num 枚食べる時に何枚パティを食べられるか計算し返す
        '''
        
        if pow(2, level + 2) - 3 == num:
            return pow(2, level + 1) - 1
        
        if num == 1:
            return 0
        elif num <= pow(2, level + 1) - 2:
            return calc_patty(level - 1, num - 1)
        elif num == pow(2, level + 1) - 1:
            return 1 + calc_patty(level - 1, num - 2)
        elif num <=  pow(2, level + 2) - 4:
            return calc_patty(level-1, pow(2, level+1)-3) + 1 + calc_patty(level-1, num - (pow(2, level + 1) - 1))
        else:
            raise RuntimeError
    print(calc_patty(n, x))

if __name__ == "__main__":
    main()

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

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


if __name__ == '__main__':
    main()

Solution (Python):
n,x = map(int,input().split())
a_list = [1]
p_list = [1]
for i in range(n):
  a_list.append(a_list[-1] * 2 + 3)
  p_list.append(p_list[-1] * 2 + 1)
def dfs(n,x):
  if x == 1:
    return 0
  if n == 1:
    if x ==2:
      return 1
    if x == 3 :
      return 2
    if x == 4 or x == 5:
      return 3
  elif 1 < x  and x <= a_list[n-1] +1:
    return dfs(n-1,x-1)
  elif x == a_list[n-1] + 2:
    return p_list[n-1] + 1
  elif a_list[n-1] + 2 < x and x <= 2 * a_list[n-1] + 2:
    return p_list[n-1] + 1 + dfs(n-1,x - (a_list[n-1] + 2))
  elif x == 2 * a_list[n-1] + 3:
    return 2 * p_list[n-1] + 1

print(dfs(n,x))

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

lengthOfBurger = [1]
numberOfPadi = [1]

for i in range(50):
    lengthOfBurger.append(1 + lengthOfBurger[-1] + 1 + lengthOfBurger[-1] + 1)
    numberOfPadi.append(numberOfPadi[-1] + 1 + numberOfPadi[-1])
A = []
def solution(k, end):
    if end == 0:
        A.append(0)
        return 0
    if end == lengthOfBurger[k]:
        A.append(numberOfPadi[k])
        return 0
    elif end == lengthOfBurger[k] + 1:
        A.append(numberOfPadi[k] + 1)
        return 0
    if end <= lengthOfBurger[k - 1] + 1:
        return solution(k - 1, end - 1)
    elif end <= lengthOfBurger[k - 1] + 2:
        return solution(k - 1, end - 1)
    elif end <= 2 * lengthOfBurger[k - 1] + 3:
        return solution(k - 1, lengthOfBurger[k - 1]+1) + solution(k - 1, end - 2 - lengthOfBurger[k - 1])
    else:
        print("NG")
        return -1

solution(n, x)

print(sum(A))