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())
def burgerLength(n):
    return(pow(2,n+2)-3)
def allpatNum(level):
    return(pow(2,level+1)-1)
def pat(level,x):
    if level == 0:
        if x==0:
            return(0)
        else:
            return(1)
    L = burgerLength(level-1)
    if x == 1:
        ans = 0
    elif x <= 1 + L:
        ans = pat(level-1,x-1)
    elif x == 2 + L:
        ans = allpatNum(level-1) + 1
    elif x < 2 + L + L:
        ans = allpatNum(level-1) + 1 + pat(level-1,x-(2+L))
    else:
        ans = allpatNum(level)
    return(ans)
print(pat(N,X))

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

def ct(n, x):
    
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x == L[n]//2+1:
        return P[n-1]+1
    elif x == L[n]:
        return P[n]
    elif x < L[n]//2+1:
        return ct(n-1,x-1)
    else:
        return P[n-1] + 1 + ct(n-1,x-(L[n]//2+1))

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

print(ct(N, X))

Solution (Python):
def depth(n):
    return 2**(n+2)-3

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

def eat(n,x):
    if n == 0:
        return x
    elif x <= 1:
        return 0
    elif x >= depth(n)-1:
        return totalp(n)
    elif x == depth(n-1) + 2:
        return totalp(n-1) + 1
    elif x > depth(n-1)+2:
        return totalp(n-1) + 1 + eat(n-1,x-depth(n-1)-2)
    else:
        return eat(n-1,x-1)

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

Solution (Python):
n, x = map(int, input().split())
ans = 0
def search(level, i):
	global ans
	
	if level == 0:
		return ans + 1
	if i == 1:
		return ans
	elif i == 2 ** (level + 2) - 3:
		return ans + 2 ** (level + 1) - 1
	elif i == 2 ** (level + 1) - 1:
		return ans + 2 ** level
	elif i < 2 ** (level + 1) - 1:
		return search(level-1, i-1)
	else:
		ans += 2 ** level
		return search(level-1, i - (2 ** (level + 1) - 1))
print(search(n, x))

Solution (Python):
N,X=map(int,input().split())
PILE=[2**(i+2)-3 for i in range(51)]
def dp(n,x):
    if x==0:
        return 0
    if n==0 and x==1:
        return 1
    if n>=1:
        bp=PILE[n-1]
        if x==1:
            return 0
        elif x<=1+bp:
            return dp(n-1,x-1)
        elif x==2+bp:
            return 1+dp(n-1,bp)
        elif 2+bp<x<=2+2*bp:
            return 1+dp(n-1,bp)+dp(n-1,x-2-bp)
        elif x==3+2*bp:
            return 1+dp(n-1,bp)*2

print(dp(N,X))

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

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

def B(L, X): 
    if L == 0: return 1
    elif X == 1: return 0
    else:
        if X <= 1 + Num[L-1]:
            return B(L-1, X-1)
        elif X == 2 + Num[L-1]:
            return B(L-1, Num[L-1]) + 1
        elif X <= 2 + 2*Num[L-1]:
            return B(L-1, Num[L-1]) + 1 + B(L-1, X - 2 - Num[L-1])
        elif X == 3 + 2 * Num[L-1]:
            return 2*B(L-1, Num[L-1]) + 1

print(B(N, X))

Solution (Python):
def calc(n, k):
	if n == 0:
		return 1
	if k == 1:
		return 0
	len = 2**(n+1)-3 
	if k <= len+1:
		return calc(n-1, k-1)
	if k == len+2:
		return calc(n-1, len)+1
	if k <= len+len+2:
		return calc(n-1, len)+1+calc(n-1, k-len-2)
	if k == len+len+3:
		return 2**(n+1)-1

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

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

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

def burger(l, y):
    if l == 0:
        return y
    if y <= l:
        return 0
    hl = heights[l]
    if y >= hl - l:
        return putties[l]

    if hl // 2 + 1 <= y:
        return putties[l - 1] + 1 + burger(l - 1, y - (hl // 2 + 1))

    return burger(l - 1, y - 1)


print(burger(n, x))

Solution (Python):
from functools import lru_cache


N, X = [int(elem) for elem in input().split()]


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

@lru_cache(None)
def num_patti(l, x):
    if x == 0:
        return 0
    elif l == 0:
        return 1
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patti(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return num_patti(l - 1, h_burger[l - 1]) + 1
        else:
            return num_patti(l - 1, h_burger[l - 1]) + 1 \
                 + num_patti(l - 1, x - h_burger[l - 1] - 2)


print(num_patti(N, X))

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

def f(N,X):
  if N==0:
    return 1
  if X<=1:
    return 0
  if X<=1+A[N-1]:
    return f(N-1, X-1)
  if X<=1+A[N-1]+1:
    return B[N-1]+1
  if X<=1+A[N-1]+1+A[N-1]:
    return B[N-1]+1+f(N-1, X-2-A[N-1])
  if X<=1+A[N-1]+1+A[N-1]+1:
    return 2*B[N-1]+1
  print N,X

print f(N,X)