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, k = map(int, input().split())


def simple(l):
    if not l:
        return "P"
    mid = simple(l - 1)
    return "B{}P{}B".format(mid, mid)


def length(l):
    return -2 + (1 - 2**(l + 2)) // (1 - 2)


def plen(l):
    return (1 - 2**(l + 1)) // (1 - 2)


def check(x, left, center, right, result):
    if x < center:
        if x == left:
            pos = -2
        else:
            return -1
    elif x > center:
        if x == right:
            pos = 2
        else:
            return 1
    else:
        pos = 0
    if pos in [-2, 0, 2]:
        if pos == -2:
            
            pass
        elif pos == 2:
            
            result += plen(depth + 1)
        else:
            
            result += plen(depth) + 1
        print(result)
        
        exit()
k -= 1




left = 0
right = length(n)
center = (left + right) // 2
result = 0
depth = n - 1

for i in range(50):
    
    
    
    
    
    
    

    pos = check(k, left, center, right, result)
    if pos == -1:
        if depth == 0:
            print(result + 1)
            exit()
        left += 1
        right = center - 1
        center = (left + right) // 2
        
    else:
        if depth == 0:
            print(result + 3)
            exit()
        right -= 1
        left = center + 1
        center = (left + right) // 2
        result += plen(depth) + 1
    
    
    depth -= 1

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

a,b = [1],[1]
for i in range(N):
    a.append(2*a[i] + 3)
    b.append(2*b[i] + 1)
def f(N,X):
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif 1 < X <= a[N-1] + 1:
        return f(N-1,X-1)
    elif X == a[N-1] + 2:
        return b[N-1] + 1
    elif a[N-1] + 2 < X <= 2*a[N-1] + 2:
        return b[N-1] + 1 + f(N-1,X-(a[N-1]+2))
    elif X == 2*a[N-1] + 3:
        return 2*b[N-1] + 1
ans = f(N,X)
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())

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 d_christmas(N, X):
    
    
    a, p = [1], [1]
    for _ in range(N):
        a.append(a[-1] * 2 + 3)
        p.append(p[-1] * 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])

    return f(N, X)

N, X = [int(i) for i in input().split()]
print(d_christmas(N, X))

Solution (Python):
n,x=map(int,input().split())
l=[0]
for i in range(n):
  l.append(2**(i+1)-1)
m=[0]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  t=2**(i+1)-1
  if x<t:
    x-=1
  elif x==t:
    c+=l[i]+1
    x=0
  else:
    c+=l[i]+1
    if x==m[i+1]:
      x-=1
    x=x-t
print(c)

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

Solution (Python):
def feed_runrun(answer, burger_dimension, appetite):
    if appetite == 0:
        return answer

    burger_size = 2 ** (burger_dimension + 2) - 3
    
    if appetite < burger_size:
        return feed_runrun(answer, burger_dimension - 1, appetite - 1)
    
    amount_of_p = 2 ** (burger_dimension + 1) - 1
    if appetite >= burger_size + 1:
        return feed_runrun(answer + amount_of_p + 1, burger_dimension, appetite - burger_size - 1)
    return feed_runrun(answer + amount_of_p, burger_dimension, appetite - burger_size)


n, x = map(int, input().split())
print(feed_runrun(0, n, x))

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

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

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

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 = [1]
P = [1]

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

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

sum = calc_pan(N, X)
print(sum)

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_patties(l, x):
    if x == 0:
        return 0
    elif l == 0:
        return 1
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patties(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return num_patties(l - 1, h_burger[l - 1]) + 1
        else:
            return num_patties(l - 1, h_burger[l - 1]) + 1 \
                 + num_patties(l - 1, x - h_burger[l - 1] - 2)


print(num_patties(N, X))

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

a, p = [1], [1]
for _ in range(N):
    a.append(a[-1] * 2 + 3)
    p.append(p[-1] * 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(2*a[i]+3)
    p.append(2*p[i]+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=[0]*(N+1)
t=1
L[0]=t
for i in range(1,N+1):
    t=2*t+3
    L[i]=t
M=[0]*(N+1)
s=1
for i in range(1,N+1):
    s=2*s+1
    M[i]=s
a=X
ans=0
for i in range(N-1,0,-1):
    t=L[i]
    s=M[i]
    if a==1:
        a-=1
        break
    elif 2<=a<=t+1:
        a-=1
    elif a==t+2:
        a-=t+2
        ans+=s+1
        break
    elif t+3<=a<=2*t+2:
        ans+=s+1
        a=a-(t+2)
    elif a==2*t+3:
        a-=2*t+3
        ans+=2*s+1
        break

if 0<=a<=4:
    ans+=max(a-1,0)
else:
    ans+=3
print(ans)

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

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

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

def main():
	n,x=map(int,input().split())
	ans = 0
	for i in range(n, -1, -1):
		if x == 0:
			break
		m = 4*(2**i)-3
		if x == m:
			ans += 2**(i+1) - 1
			break
		if x >= (m+1)/2:
			ans += 2**(i)
			x -= int((m+1)/2)
		else:
			x -= 1
	print(ans)
	return
main()

Solution (Python):
p = [1]*51
t = [1]*51
def f(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    if x==t[n]:
        return p[n]
    if x==p[n]:
        return p[n-1]+1
    if x<p[n]:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-p[n])+1

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

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

sum_p = [1]
sum_dim = [1]

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


def cal(n, rem):
    if n == 0:
        return 0 if rem<= 0 else 1
    elif rem <= 1 + sum_dim[n-1]:
        return cal(n - 1, rem - 1)
    else:
        return sum_p[n-1] + 1 + cal(n - 1, rem - 2 - sum_dim[n-1])


print(cal(n, x))

Solution (Python):
a = [1 for i in range(51)]
p = [1 for i in range(51)]


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


def main():
    N, X = map(int, input().split())
    for i in range(N):
        a[i+1] = 2 * a[i] + 3
        p[i+1] = 2 * p[i] + 1
    ans = get(N, X)
    print(ans)


if __name__ == "__main__":
    main()

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

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

def r(n,x):
    if x<=n:
        return 0
    if x==H[n]:
        return P[n]
    if x>=H[n-1]+2:
        return P[n-1]+1+r(n-1,x-H[n-1]-2)
    else:
        return r(n-1,x-1)

print(r(N,X))

Solution (Python):
p = [1]*51
t = [1]*51
def f(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    if x==t[n]:
        return p[n]
    if x==p[n]:
        return p[n-1]+1
    if x<p[n]:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-p[n])+1

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

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

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

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

print(f(N, X))

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

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

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

def solve(L, X):
    if L == 0:
        return 0 if X == 0 else 1
    if X == 1:
        return 0
    if 1 < X <= 1 + a(L-1):
        return solve(L-1, X-1)
    if X == 2 + a(L-1):
        return p(L-1) + 1
    if 2 + a(L-1) < X <= 2 + 2 * a(L-1):
        return p(L-1) + 1 + solve(L-1, X-a(L-1)-2)
    if X == 3 + 2 * a(L-1):
        return 2 * p(L-1) + 1

print(solve(N, X))

Solution (Python):


from sys import stdin, stderr

DPL = [0] * 56
DPP = [0] * 56

def F(n, x):
   if x == 0:
      return 0

   if x == 1:
      return 1 if n == 0 else 0

   if x == DPL[n]:
      return DPP[n]

   if x == 1 + DPL[n-1] + 1:
      return DPP[n-1] + 1
   elif x > 1 + DPL[n-1] + 1:
      return DPP[n-1] + 1 + F(n-1, x - (1 + DPL[n-1] + 1))
   else:
      return F(n-1, x-1)

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

   DPL[0] = 1
   DPP[0] = 1
   for n in xrange(1, N+1):
      DPL[n] = 2*DPL[n-1] + 3
      DPP[n] = 2*DPP[n-1] + 1

   res = F(N, X)
   print(res)

   return 0

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

bagaAtsusas=[]
bagaAtsusasP=[]
def bagaAtsusa(number):
  if number==0:
    bagaAtsusas.append(1)
    return 1
  else:
    tmp=3+ bagaAtsusa(number-1)*2
    bagaAtsusas.append(tmp)
    return tmp

def bagaAtsusaP(number):
  if number==0:
    bagaAtsusasP.append(1)
    return 1
  else:
    tmp=1 + bagaAtsusaP(number-1)*2
    bagaAtsusasP.append(tmp)
    return tmp


def donoBaga(bagaLevel,fukasa,numList,ans):
  if(fukasa==1):
    numList[bagaLevel-1]=0
    
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    print(ans)
  elif(fukasa<bagaAtsusas[bagaLevel-1]+1):
    
    numList[bagaLevel-1]=0
    fukasa=fukasa-1
    donoBaga(bagaLevel-1,fukasa,numList,ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]+1):
    numList[bagaLevel-1]=1
    
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    print(ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]+2):
    numList[bagaLevel-1]=1
    
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
  elif(fukasa<bagaAtsusas[bagaLevel-1]*2+2):
    
    numList[bagaLevel-1]=1
    fukasa=fukasa-(bagaAtsusas[bagaLevel-1]+2)
    ans=ans+1
    donoBaga(bagaLevel-1,fukasa,numList,ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]*2+2):
    numList[bagaLevel-1]=2
    
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]*2+3):
    numList[bagaLevel-1]=2
    
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
    
bagaAtsusa(n)
bagaAtsusaP(n)
numList=[0]*n
ans=0
donoBaga(n,x,numList,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 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())
L2 = [1]
j = 1
for i in range(N+2):
    j *= 2
    L2.append(j)
Y = 0
for i in range(N+1):
    if L2[N+1-i] - 1 == X:
        Y += L2[N-i]
        print(Y)
        break
    elif L2[N+2-i] - 3 == X:
        Y += L2[N+1-i] - 1
        print(Y)
        break
    elif L2[N+1-i] - 1 < X:
        Y += L2[N-i]
        X -= L2[N+1-i] - 1
    else:
        X -= 1
else:
    print(Y)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
N,X = map(int,input().split())
def n_barg_hight(n):
	if(n == 0):
		return 1

	L1barg_height = n_barg_hight(n-1)
	Lbarg_height = 1 + L1barg_height + 1 + L1barg_height + 1
	return Lbarg_height

def n_barg_pat(n):
	if(n == 0):
		return 1
	L1barg_pat = n_barg_pat(n-1)
	Lbarg_pat = 1 + L1barg_pat*2
	return Lbarg_pat


def answer(N,X):

	if(X == 1):
		if(N == 0):
			return 1
		else:
			return 0
	
	elif(X == n_barg_hight(N)):
		return n_barg_pat(N)

	elif(X == n_barg_hight(N)//2 + 1):
		return n_barg_pat(N-1)+1

	elif(X <= n_barg_hight(N)//2):
		return answer(N-1,X-1)

	elif(X > n_barg_hight(N)//2 + 1):
		Lbarg = n_barg_pat(N-1) + answer(N-1,X-n_barg_hight(N-1)-2) +1
		return Lbarg


print(answer(N,X))

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

num = 1
pate = 1
for i in range(n):
    num = num * 2 + 3
    pate = pate * 2 + 1

def culc(l, idx, num, pate):
    npate = (pate - 1) // 2
    nnum = (num - 3) // 2
    mid = (num + 1) // 2
    if l == 1:
        if idx == 0:
            return 0
        elif idx == 1:
            return 0
        elif idx == 2:
            return 1
        elif idx == 3:
            return 2
        elif idx == 4:
            return 3
        else:
            return 3
    elif mid == idx:
        return npate + 1
    elif mid < idx:
        return npate + 1 + culc(l - 1, idx - mid, nnum, npate)
    else:
        return culc(l - 1, idx - 1, nnum, npate)
print(culc(n, x, num, pate))

Solution (Python):
N,X=map(int,input().split())
Z=[0]+[ 2**(i+2) -3 for i in range(N+1)]
B=[0]+[ 2**(i+1) -2 for i in range(N+1)]
P=[0]+[ 2**(i+1) -1 for i in range(N+1)]
ans=0
def arg(l,i):
    global ans
    if l != 0 :
        if Z[l]/2+1/2 < i :
            ans += (1 + P[l-1])

            return  arg( l-1 , i-( (Z[l]-1)/2 + 1 ) ) 

        elif Z[l]/2 +1/2  > i :
 
            return arg( l-1 , i - 1)

        else :
            ans += P[l-1] + 1
        
    else :
        pass
arg(N+1,X)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)

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

num = [0] * (n + 1)
num_p = [0] * (n + 1)
num_h = [0] * (n + 1)
num[0] = 1
num_p[0] = 1

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

for i in range(n + 1):
    num_h[i] = num[i] // 2 + 1


def func(idx, n):
    if idx == 1 and n == 0:
        return 1
    if idx == 1 and n == 1:
        return 0
    if idx <= n or n < 0:
        return 0

    if idx == num_h[n]:
        ret = num_p[n - 1] + 1

    elif idx > num_h[n]:
        ret = num_p[n] - func(num[n] - idx - 1, n - 1)

    elif idx < num_h[n]:
        ret = func(idx - 1, n - 1)

    return ret

print(func(x, n))

Solution (Python):
n_x = input()
n_x_list =n_x.split(' ')

N = int(n_x_list[0])
X = int(n_x_list[1])

















def L(N):
    return 2 ** (N+2) - 3

def P(N):
    return 2 ** (N+1) - 1

def solve(N, X):
    half_l = int(L(N) / 2)
    if N == 0 and X >= 1:
        return 1
    elif N == 0 and X == 0:
        return 0

    if half_l <= 1:
        return 0
    elif X < half_l:
        return solve(N - 1, X - 1)
    elif X == half_l:
        return P(N-1)
    elif X == half_l + 1:
        return P(N-1) + 1
    elif half_l + 1 < X:
        return P(N-1) + 1 + solve(N-1, (X - L(N-1) - 2))
    elif half_l * 2 + 3 == X:
        return 2 * P(N-1) + 1


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

Solution (Python):
n,x=map(int,input().split())
len_b=2**(n+2)-3
p=[2**(i+1)-1 for i in range(n)]
start=1
end=len_b
center=(end+1)//2
count1=0
count2=n-1
while True:
    if count2==-1:
        count1+=1
        break
    elif x==start:
        break
    elif x==center:
        count1+=p[count2]+1
        break
    elif x==end:
        count1+=p[count2]*2+1
        break
    elif x<center:
        start=start+1
        end=center-1
        center=(start+end)//2
        count2-=1
    else:
        start=center+1
        end=end-1
        center=(start+end)//2
        count1+=p[count2]+1
        count2-=1
print(count1)

Solution (Python):
n,k = map(int,input().split())
pk = [1]
pz = [1]
for i in range(n):
  pk.append(pk[-1]*2+1)
  pz.append(pz[-1]*2+3)
ans = 0
for i in range(n,-1,-1):
  z = pz.pop()
  ka = pk.pop()
  if k>= z//2:
    ans += ka//2
    k-=z//2
    if k:
      ans+=1
  if k:
    k-=1
print(ans)

Solution (Python):
n,x=map(int,input().split())
l=[]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    x=0
  elif x>2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    elif x==m[i]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)

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

    n_layers_at_level = {0: 1}
    n_patties_at_level = {0: 1}
    for i in range(1, n):
        n_layers_at_level[i] = 2 * n_layers_at_level[i-1] + 3
        n_patties_at_level[i] = 2 * n_patties_at_level[i-1] + 1

    def amount_of_patties_from_bottom(level, n_layer):
        if level == 0:
            return 1

        lower_level_n_layer     = n_layers_at_level[level-1]
        lower_level_n_patties   = n_patties_at_level[level-1]
        mid_point = lower_level_n_layer + 2

        ret = 0
        if n_layer <= 1:
            ret = 0
        elif n_layer <= mid_point:
            if n_layer == mid_point:
                ret += 1
            ret += amount_of_patties_from_bottom(level - 1, n_layer - 1)
        else:
            ret += 1 + lower_level_n_patties
            ret += amount_of_patties_from_bottom(level - 1, n_layer - mid_point)
        return ret

    print(amount_of_patties_from_bottom(n, x))
    return


main()

Solution (Python):



al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx):
    if idx == 1:
        if x >= 5:
            return ans + 3
        if x <= 0:
            return ans
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
    return solve2(ans, x, idx - 1)


def solve():
    n, x = map(int, input().split())
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    print(solve2(0, x, n))


if __name__ == "__main__":
    solve()

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

answer = 0
red = x

searching_index = n
while red > 0:
    for i in reversed(range(searching_index + 1)):
        length = 2**(i + 2) - 3
        if red >= length:
            if red >= length + 1:
                answer += 1
                red -= 1
            searching_index = i
            answer += 2**(i+1) - 1
            red -= length
            break
        red -= 1

print(answer)

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

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

Solution (Python):



import math

al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx, cnt):
    if idx == 1:
        if x >= 5:
            return ans + 3
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
        if x <= 0:
            return ans
    return solve2(ans, x, idx - 1, cnt)


def solve(n, x):
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    ans = solve2(0, x, n, 0)
    print(ans)


if __name__ == "__main__":
    n, x = map(int, input().split())
    solve(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, raw_input().split())

a,p=[1], [1]
for i in range(N):
	a.append(a[-1]*2+3)
	p.append(p[-1]*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 <= 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())

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

ans = 0
while 0<X:
    if(X<((HforL[N]-3)/2)+1):
        X -= 1
        N -= 1
        continue
    if(X==((HforL[N]-3)/2+1)):
        ans+=PforL[N-1]
        break
    if(X==((HforL[N]-3)/2+2)):
        ans+=PforL[N-1]+1
        break
    if(X<HforL[N]-1):
        ans += PforL[N-1]+1
        X -= 2+HforL[N-1]
        N -= 1
        continue
    if(X<=HforL[N]):
        ans += PforL[N]
        break
print(ans)

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


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]

b = [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]



def f(k,x,a,b):
    if x == 0:
        return 0
    elif k == 0:
        return 1
    elif k== 1:
        if x <= 4:
            return x-1
        else:
            return 3
    else:
        if x == (a[k]-1)//2+1:
            return b[k-1] + 1
        elif x < (a[k]-1)//2+1:
            if x <= k:
                return 0
            else:
                return f(k-1,x-1,a,b)
        elif x >= a[k]-k:
            return b[k]
        else:
            return b[k-1] + f(k-1,x-(a[k]-1)//2-1,a,b) + 1

print(f(n,x,a,b))

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

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

res = 0
while n >= 0:
    if n == 0:                 
        res += 1
        break
    elif x == 0:               
        break
    elif x == l[n] - 1:        
        res += p[n]
        break
    elif x == l[n] // 2:       
        res += p[n-1] + 1
        break
    elif x > l[n] // 2:        
        res += p[n-1] + 1
        x -= l[n-1] + 2
        n -= 1
    else:                      
        n -= 1
        x -= 1

print(res)

Solution (Python):

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

p = [0 for _ in range(N+1)]
b = [0 for _ in range(N+1)]
t = [0 for _ in range(N+1)]
p[0] = 1
t[0] = 1
idx = 0
for i in range(1,N+1):
    p[i] = p[i-1]*2 + 1
    b[i] = b[i-1]*2 + 2
    t[i] = p[i]+b[i]
    if X == t[i]:
        print(p[i])
        exit()
    if t[i-1] < X < t[i]:
        idx = i

if X <= N:
    print(0)
    exit()

start = X
ans = 0
for i in reversed(range(1,N+1)):
    if t[i] - i <= start <= t[i]:
        ans += p[i]
        print(ans)
        exit()

    if t[i]//2 == start:
        ans += p[i-1]
        print(ans)
        exit()

    if t[i]//2 + 1 == start:
        ans += p[i-1] + 1
        print(ans)
        exit()

    if t[i]//2 + 1 < start < t[i] - i:
        ans += p[i-1] + 1
        start = start - t[i-1] - 2
    else:
        start = start - 1

print(ans)

Solution (Python):
import sys
def qwe(n,x,ans):
    n1 = "BPPPB"
    n2 = "BBPPPBPBPPPBB"
    if n==1:
        for s in n1:
            if s=="P": ans+=1
            x-=1
            if x==0:
                print(ans)
                sys.exit()
    else:
        for s in n2:
            if s=="P": ans+=1
            x-=1
            if x==0:
                print(ans)
                sys.exit()

def main():
    n,x = map(int, input().split())
    if n<=2:
        qwe(n,x,0)
    a = [1]
    b = [1]
    for i in range(n-1):
        a.append(2*a[-1]+3)
        b.append(2*b[-1]+1)
    ans = 0
    if x== 2*a[n-1]+3:
        print(2*b[n-1]+1)
        sys.exit()
    elif x==2*a[n-1]+2:
        print(2*b[n-1]+1)
        sys.exit()
    elif x == a[n-1]+2:
        print(b[n-1]+1)
        sys.exit()
    elif x== a[n-1]+1:
        print(b[n-1])
        sys.exit()
    elif x > a[n-1]+2:
        ans += b[n-1]+1
        x -= a[n-1]+2
        n = n-1
    else:
        x -=1
        n = n-1
    while n>2 or x > 0:
        if x== 2*a[n-1]+3:
            ans += 2*b[n-1]+1
            print(ans)
            sys.exit()
        elif x==2*a[n-1]+2:
            ans += 2*b[n-1]+1
            print(ans)
            sys.exit()
        if x == a[n-1]+2:
            ans += b[n-1]+1
            print(ans)
            sys.exit()
        elif x== a[n-1]+1:
            ans+=b[n-1]
            print(ans)
            sys.exit()
        elif x > a[n-1]+2:
            ans += b[n-1]+1
            x -= a[n-1]+2
            n = n-1
        else:
            x -=1
            n = n-1
    if x==0:
        print(ans)
        sys.exit()
    qwe(n,x,ans)
if __name__ == "__main__":
    main()

Solution (Python):
lens=[1 for _ in range(51)]
nump=[1 for _ in range(51)]
for i in range(50):
    lens[i+1]=2*lens[i]+3
    nump[i+1]=2*nump[i]+1
def level(n):
    return max(lvl for lvl,ln in enumerate(lens) if ln<=n)

def calc():
    table={}
    def _calc(l,x):
        if x==0:
            return 0
        if (l,x) in table:
            return table[(l,x)]
        if x==lens[l]:
            res=nump[l]
        elif x<=lens[l-1]:
            res=_calc(l-1,x-1)
        elif x==lens[l-1]+1:
            res=nump[l-1]
        elif x==lens[l-1]+2:
            res=nump[l-1]+1
        else:
            res=nump[l-1]+1+_calc(l-1,x-lens[l-1]-2)
        table[(l,x)]=res
        return res
    return _calc
whole=calc()
print(whole(*map(int,input().split())))

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

cnt = [0,1]
tmp = [[0,1]]

for i in range(n):

    tmp.append([cnt[0] * 2 + 2,cnt[1] * 2 + 1])
    cnt[0] = cnt[0] * 2 + 2
    cnt[1] = cnt[1] * 2 + 1

"""
半分に区切ってジャスト半分なら前の分+1を出力
大きければ前の分+1を足して次
小さければ数える数を1小さくしてレベルを下げる
"""
num = 0
for i in range(n,0,-1):
    if (sum(tmp[i])+1)/2 == k:
        num += tmp[i-1][1]+1
        break
    elif (sum(tmp[i])-1)/2 == k:
        num += tmp[i-1][1]
        break
    elif sum(tmp[i]) == k or sum(tmp[i])-1 == k:
        num += tmp[i][1]
        break
    elif (sum(tmp[i])-1)/2 < k:
        num += tmp[i-1][1]+1
        k = k - sum(tmp[i-1]) - 2
    elif (sum(tmp[i])-1)/2 > k:
        k = k - 1
print(num)

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

def func(l=N, x=X):
	if (l == 0):
		if (x >= 1):
			return 1
		else:
			return 0
	if (x < fcnt[l-1]+2):
		return func(l-1, x-1)
	else:
		return pcnt[l-1]+1+func(l-1, x-fcnt[l-1]-2)

print(func())