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):
def PAndB(n):
    return (2 ** (n + 2)) - 3


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


def count(N, X):
    if N == 0:
        return 1
    elif X <= N:
        return 0
    elif X >= PAndB(N) - (N - 1):
        return allPatty(N)
    elif X == PAndB(N - 1) + 2:
        return allPatty(N - 1) + 1
    elif X <= PAndB(N - 1) + 1:
        return count(N - 1, X - 1)
    else:
        return allPatty(N - 1) + 1 + count(N - 1, X - (PAndB(N - 1) + 2))


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


if __name__ == '__main__':
    main()

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




def find_level(lv, x):
    

    if lv == 0:
        return 1
    
    midlv = L[lv-1] + 2
    
    
    if x == L[lv]:

        ret = P[lv]
    
    elif x < L[lv] and x > midlv:

        ret = find_level(lv-1,x - midlv) + 1 + P[lv-1]
    
    elif x == midlv:

        ret = 1 + P[lv-1] 
    
    elif x < midlv and x > 1:

        ret = find_level(lv-1, x - 1)
    
    else:

        ret = 0
        
    return(ret)

r = find_level(N, X)
print(r)

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

table_l = [-1 for _ in range(51)]
table_p = [-1 for _ in range(51)]
table_l[0] = 1
table_p[0] = 1

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


def f(level, x):
    if level == 1:
        if x == 0 or x == 1:
            return 0
        if x == 2:
            return 1
        if x == 3:
            return 2
        else:
            return 3

    if table_l[level] == x:
        return table_p[level]

    if x - 1 <= table_l[level - 1]:
        return f(level - 1, x - 1)

    if x - 2 == table_l[level - 1]:
        return table_p[level - 1] + 1
    if x - 2 > table_l[level - 1]:
        xx = x - 2 - table_l[level - 1]
        return table_p[level - 1] + 1 + f(level - 1, xx)


print(f(n, x))

Solution (Python):
def main():
    """
    input:
        1 <= N <= 50
        1 <= X <= レベル N バーガーの層の総数

    レベル L バーガー
        バン 1枚
        レベル L−1バーガー
        パティ 1枚
        レベル L−1バーガー
        バン 1枚
    この順に下から積み重ねたもの

    output:
        N! の約数のうち、七五数 は何個
        七五数とは約数をちょうど 75個持つ正の整数
    """
    N, X = map(int, input().split())

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


def layers(N):
    layer = [0] * (N + 1)
    layer[0] = 1
    p_layer = [0] * (N + 1)
    p_layer[0] = 1

    for i in range(1, N+1):
        layer[i] = 1 + layer[i-1] + 1 + layer[i-1] + 1
        p_layer[i] = p_layer[i-1] + 1 + p_layer[i-1]

    return layer, p_layer


def f(N, X):
    """
    差分は4から始まって2倍になる
    2^32 < layer 50 < 2^64

    下からX層を食べるので端から考える
    """
    layer, p_layer = layers(N)

    def patty(N, X):
        if N <= 0:
            return 0

        ans = 0
        
        if X >= 1:
            X -= 1
            
            if X >= layer[N-1]:
                X -= layer[N-1]
                ans += p_layer[N-1]
                
                if X >= 1:
                    X -= 1
                    ans += 1
                    
                    if X >= layer[N-1]:
                        X -= layer[N-1]
                        ans += p_layer[N-1]
                        
                    else:
                        ans += patty(N-1, X)
            else:
                ans += patty(N-1, X)

        return ans

    ans = patty(N, X)
    return ans


if __name__ == '__main__':
    main()

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 <= 1):
		return 0
	if (x < fcnt[l-1]+2):
		return func(l-1, x-1)
	elif (x == fcnt[l - 1] + 2):
		return pcnt[l-1]+1
	else:
		return pcnt[l-1]+1+func(l-1, x-fcnt[l-1]-2)

print(func())

Solution (Python):
class Burg:
    def __init__(self):
        self.lv = [2**(i+1) - 1 for i in range(51)]

    def make_burg(self, n, m):
        if n == 0:
            return 1, m - 1
        num = 4 * 2**n - 3
        if num <= m:
            return self.lv[n], m - num
        if m <= 1:
            return 0, 0
        a, b = self.make_burg(n - 1, m - 1)
        if b <= 1:
            return a + b, 0
        c, d = self.make_burg(n - 1, b - 1)
        return a + c + 1, max(0, d - 1)

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

gen = Burg()
print(gen.make_burg(n, x)[0])

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

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

def lune(n,x):
    if n == 0 and x > 0:
        return 1
    for i in range(1,n+1):
        if x > h(n-i) + i:
            return (p(n-i) + 1 + lune(n-i, x - (h(n-i) + i) - 1))
    if x > n:
        return 1
    else:
        return 0

def main():
    n,x = map(int, input().split())
    if x >= (h(n) + 1) // 2:
        print(p(n) - lune(n, h(n) - x))
    else:
        print(lune(n,x))

if __name__ == "__main__":
    main()

Solution (Python):
N, X = (int(i) for i in input().split())

import math

def Pn(n):
    x = 0
    for i in range(n):
        x = x + 2**i
        yield x

Paty = list(Pn(N+1))
Bager = [2*i -1 for i in Paty]

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

    harf = (Bager[n] + 1) // 2

    if x == harf:
        return 1 + Paty[n-1]

    if x > harf:
        return Ln(n-1, x - 2 - Bager[n-1]) + Paty[n-1] + 1
    else:
        return Ln(n-1, x-1)

print(Ln(N, X))

Solution (Python):
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N,X = map(int,input().split())
X-=1

P = [0,1]

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

left = 0
right = 1
for i in range(N):
    right = right*2 + 3

mid = int((right-left)/2)
ans = 0

while(left <= right):
    if(X<mid):
        right = mid-1
        left += 1
        N-=1
    elif (X>mid):
        left = mid+1
        right -= 1
        ans = ans + P[N] + 1
        N-=1
    else:
        ans = ans + P[N] + 1
        break

    mid = left+int((right-left)/2)
    
print(ans)

Solution (Python):
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def print_and_exit(X, eated_P):
    if X == 0:
        print eated_P
        exit()

table = {}

def get_burger_size(L):
    global table
    if L in table:
        return table[L]
    if L == 0:
        table[0] = (1L, 1L)
        return (1L, 1L)

    l_1_burger = get_burger_size(L - 1)
    table[L - 1] = l_1_burger
    return  (3L + 2L * l_1_burger[0], 1L + 2L * l_1_burger[1])

g_eated = 0
g_eated_P = 0

def calc_eated(X, L, eated_P):
    X -= 1
    print_and_exit(X, eated_P)

    (eated_f, eated_P_f) = get_burger_size(L - 1)
    if X < eated_f:
        calc_eated(X, L - 1, eated_P)
    X -= eated_f
    eated_P += eated_P_f
    print_and_exit(X, eated_P)

    eated_P += 1
    X -= 1
    print_and_exit(X, eated_P)

    (eated_f, eated_P_f) = get_burger_size(L - 1)
    if X < eated_f:
        calc_eated(X, L - 1, eated_P)
    X -= eated_f
    eated_P += eated_P_f
    print_and_exit(X, eated_P)

    X -= 1
    print_and_exit(X, eated_P)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, X] = [long(input_raw[0]), long(input_raw[1])]
    calc_eated(X, N, 0)


if __name__ == '__main__':
    main()

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

ans = 0
i = n
jouken = False
while True:
    if i == 0:
        if x ==1:
            ans += 1
        break
    if x==1:
        break
    if x == su[i]:
        ans+=a[i]
        break
    if x == int(su[i]/2) +1:
        ans += a[i-1] +1
        break
    elif x < int(su[i]/2)+1:
        i -= 1
        x -= 1
    elif x > int(su[i]/2)+1:
        i -= 1
        ans += a[i]+1
        x -= su[i]
        x -= 2

print(ans)

Solution (Python):

ls_len = [1]
ls_p = [1]
for i in range(50):
    ls_len.append(2*ls_len[-1]+3)
    ls_p.append(1+2*ls_p[-1])
n,x = map(int,input().split())

def calc_p(level,x):
    if level == 0:
        return 1
    elif x == ls_len[level]-1:
        return ls_p[level]
    elif x == 0:
        return 0
    elif x == (ls_len[level]-1)/2:
        return ls_p[level-1]+1
    elif x < (ls_len[level]-1)/2:
        return calc_p(level-1,x-1)
    else:
        return calc_p(level-1,x-2-ls_len[level-1])+ls_p[level-1]+1
print (calc_p(n,x-1))

Solution (Python):
l = [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]

n, x = [int(i) for i in input().split()]
h = l[n]
e = 0
for i in range(n)[::-1]:
    if x >= 1 :
        x -= 1
    else:
        break
    if x >= l[i]:
        x -= l[i]
        e += p[i]
    else:
        continue
    if x >= 1 :
        x -= 1
        e += 1
    else:
        break
    if x >= l[i]:
        x -= l[i]
        e += p[i]
    else:
        continue
print(e)

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

pl = [1]
pa = [1]

for i in range(n):
    tmpp = pl[-1]
    tmpa = pa[-1]
    pl.append(tmpp*2+1)
    pa.append(tmpa*2+3)

def largest(n,x):
    if x <= 0:
        return 0
    else:
        if n <= 0:
            if x >= 4:
                return 3
            else:
                return x
        else:
            if x > pa[n]:
                return pl[n] + 1 + largest(n-1, x-2-pa[n])
            elif x == pa[n]:
                return pl[n]
            else:
                return largest(n-1,x-1)

print(largest(n,x))

Solution (Python):
N,X = map(int,input().split())
def lb(N):
    if N != 0:
        return 2*lb(N-1)+3
    else:
        return 1
def pn(N):
    if N != 0:
        return 2*pn(N-1)+1
    else:
        return 1
def B(N,X):
    if X == 0:
        return 0
    elif N == 0:
      	return 1
    elif lb(N-1)+1 >= X:
        return B(N-1,X-1)
    else:
        return pn(N-1)+1+B(N-1,X-lb(N-1)-2)
print(B(N,X))

Solution (Python):
n, x = map(int, input().split())
def all_putty(m):
 return 2**(m+1)-1
count = 0
for l in range(n+1)[::-1]:
  mark = 2**(1+l)-1
  if x >= mark:
    count += all_putty(l-1) +1
    x -= mark
  else:
    x -= 1
print(count)

Solution (Python):

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

def count(level, pos):
    L_child = 2 ** ((level - 1) + 2) - 3
    P_child = 2 ** ((level - 1) + 1) - 1
    
    if pos == 0: return 0 if level > 0 else 1
    elif pos < L_child + 1: return count(level - 1, pos - 1)
    elif pos == L_child + 1: return P_child + 1
    elif L_child + 1 < pos < 2 * (L_child + 1):
        return P_child + 1 + count(level - 1, pos - (L_child + 2))
    else: return 2 * P_child + 1

print(count(N, X - 1))

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

burger = [1]
pati = [1]
for i in range(1,52):
    burger.append(burger[i-1]*2+3)
    pati.append(pati[i-1]*2+1)
    
def calc(l, eat):
    if l == 0:
        return 1
    elif eat == 1:
        return 0
    elif eat <= burger[l-1]+1:
        return calc(l-1, eat-1)
    elif eat == burger[l-1]+2:
        return pati[l-1] + 1
    elif eat <= (burger[l-1]+1)*2:
        return calc(l-1, eat-(2+burger[l-1])) + pati[l-1] + 1
    elif eat == (burger[l-1]*2) + 3:
        return (2*pati[l-1]) + 1

print(calc(N, X))

Solution (Python):
import numpy as np
def niku(level, num):
	maisu = 2**(level+2)-3
	if(num <= level):
		return 0
	elif(level == 0):
		return 1
	elif(num < (maisu+1)/2):
		return niku(level-1, num-1)
	elif(num == (maisu+1)/2):
		return 2**(level+1-1)-1+1
	else:
		return 2**(level+1-1)-1+1+niku(level-1, num-((maisu+1)/2))

def main():
	
	buf = input().split()
	n = int(buf[0])
	x = int(buf[1])
	print(niku(n, x))
		
main()

Solution (Python):


n,x=[int(x) for x in input().split()]
burgurnum=["" for _ in [0]*51]
burgurnumP=["" for _ in [0]*51]
def burgurNumFunc(level):
    if burgurnum[level]=="":
        if level==0:
            burgurnum[level]=1
        else:
            burgurnum[level]=burgurNumFunc(level-1)*2+3
    return burgurnum[level]
def burgurnumPFunc(level):
    if burgurnumP[level]=="":
        if level==0:
            burgurnumP[level]=1
        else:
            burgurnumP[level]=burgurnumPFunc(level-1)*2+1
    return burgurnumP[level]
    
    
def burger(num,level):
    if level==0:
        return 1
    elif num==1:
        return 0
    elif 1<num<=1+burgurNumFunc(level-1):
        return burger(num-1,level-1)
    elif num==burgurNumFunc(level-1)+2:
        return burgurnumPFunc(level-1)+1
    elif burgurNumFunc(level-1)+2<num<=burgurNumFunc(level-1)*2+2-1:
        return burgurnumPFunc(level-1)+1+burger(num - burgurNumFunc(level-1)-2,level-1)
    else:
        return burgurnumPFunc(level-1)*2+1
    

print(burger(x,n))

Solution (Python):
n, x = map(int, input().split())
bli = []
pli = []
z = 2 ** (n + 2) - 3
count = 0
for i in range(n + 1):
    y = 2 ** (i + 2) - 3
    bli.append(y // 2 + 1)
    pli.append(y // 2)
for i in range(n, -1, -1):
    if x == 0:
        break
    elif i == 0:
        count += 1
        break
    elif x > (2 ** (i + 2) - 3) // 2 + 1:
        count += bli[i - 1] + 1
        x -= (2 ** (i + 2) - 3) // 2
    elif x == (2 ** (i + 2) - 3) // 2 + 1:
        count += bli[i - 1] + 1
        break
    x -= 1
print(count)

Solution (Python):
def abc115_d():
    n, x = map(int, input().split())
    l = [1] * 51
    p = [1] * 51
    for i in range(50):
        l[i + 1] = 2 * l[i] + 3
        p[i + 1] = p[i] * 2 + 1

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

    print(ans)


abc115_d()

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

def eat(n,x):
    if x<=1: return 0
    if x==l[n-1]+1: return bg[n-1]
    if x==l[n] or x==l[n]-1: return bg[n]
    if x<=l[n-1]: return eat(n-1,x-1)
    return bg[n-1]+1+eat(n-1,x-l[n-1]-2)
print(eat(N,X))

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

Solution (Python):
memo = {}


def solve(N, X):
    if (N, X) not in memo:
        l = (pow(2, N + 2) - 3)
        l2 = (l - 3) // 2 + 1
        if N == 0:
            return 1
        if X == 1:
            return 0
        elif X <= l2:
            memo[(N, X)] = solve(N - 1, X - 1)
        elif X == l2 + 1:
            memo[(N, X)] = solve(N - 1, l2 - 1) + 1
        elif X < l:
            left = solve(N - 1, l2 - 1)
            right = solve(N - 1, X - 1 - l2)
            memo[(N, X)] = left + 1 + right
        elif X == l:
            memo[(N, X)] = solve(N - 1, l2 - 1) * 2 + 1
    return memo[(N, X)]


if __name__ == "__main__":
    N, X = tuple(map(int, input().split(" ")))
    print(solve(N, X))

Solution (Python):
import pdb

def eat(n, x):
    ret = 0

    if x == 0:
        return 0, x

    if n == 0:
        x -= 1
        return 1, x

    if allnum[n] <= x:
        x -= allnum[n]
        return pnum[n], x
        
    
    x -= 1 
    if x == 0:
        return 0, x

    
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    
    x -= 1
    ret += 1
    if x == 0:
        return ret, x

    
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    
    x -= 1 
        
    return ret, x


def main():
    tmp = input().split()
    n = int(tmp[0])
    x = int(tmp[1])
    global pnum
    global allnum
    pnum = [1]
    allnum = [1]
    for i  in range(1, 51):
        pnum.append(pnum[i-1] * 2 + 1)
        allnum.append(allnum[i-1] * 2 + 3)

    ans, tmp = eat(n, x)

    print(ans)

        
if __name__ == '__main__':
    main()

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

N,X = (int(i) for i in input().split(' '))

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





def find_level(lv, x):
    

    if lv == 0:
        return 1
    
    midlv = L[lv-1] + 2
    
    
    if x == L[lv]:

        return  P[lv]
    
    if x < L[lv] and x > midlv:

        return find_level(lv-1,x - midlv) + 1 + P[lv-1]
    
    elif x == midlv:

        return 1 + P[lv-1] 
    
    elif x < midlv and x > 1:

        return find_level(lv-1, x - 1)
    
    else:

        return 0
        
    return(ret)

r = find_level(N, X)
print(r)

Solution (Python):
n,x=map(int,input().split())
def b(n,x):
  if n==0 and x==1:
    return 1
  while n>0:
    z=(2**(n+2)-3)//2+1
    if x==1:
      return 0
    elif 1<x<z:
      return b(n-1,x-1)
    elif x==z:
      return 2**n
    elif z<x<(2**(n+2)-3):
      return 2**n + b(n-1,x-z)
    else:
      return 2**(n+1)-1
print(b(n,x))

Solution (Python):
burgerLens = [1 + 4 * (1 - 2**i)/(1-2) for i in range(0,51)]
numPatties = [1 + 2 * (1 - 2**i)/(1-2) for i in range(0,51)]

def recurse(n,k):
    if n == 0:
        return numPatties[0]
    if k <= n:
        return 0
    
    mid = burgerLens[n] // 2 + 1
    if k == mid:
        return 1 + numPatties[n-1]
    if k < mid:
        return recurse(n-1,k-1)
    if k > mid:
        return 1 + numPatties[n-1] + recurse(n-1,k-2-burgerLens[n-1])
    
N,K = map(int,input().split())
print(int(recurse(N,K)))

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

patty = []
patty.append(1)

lay = []
lay.append(1)

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





c = 0

for i in reversed(range(n+1)):
 
    if x == lay[i]:
      
        c += patty[i]
        break

    elif x == lay[i-1]+2:  
       
        c += patty[i-1]+1
        break
    elif x < lay[i-1]+2:  
        
        x = x-1
    else:  
     
        x = x-2-lay[i-1]
        c += patty[i-1]+1

print(c)

Solution (Python):
def p_count(a, b):
    global l
    if b <= 0:
        return 0
    if a <= 0:
        return 1
    else:
        if b <= int(l[a][1]/2):
            return p_count(a-1, b-1)
        else:
            c = b - int(l[a][1]/2) - 1
            return l[a-1][0] + 1 + p_count(a-1, c)

l=list([[1,1]])
n,x = (int(i) for i in input().split())

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

print(p_count(n,x))

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


def all_pat_num(level):
    return(pow(2, level + 1) - 1)


def pat(level, x):
    if level == 0:
        if (x == 0):
            return 0
        else:
            return 1
    L = pow(2, level + 1) - 3
    if x == 1:
        ans = 0
    elif x <= 1 + L:
        ans = pat(level-1,x-1)
    elif x == 2 + L:
        ans = all_pat_num(level-1) + 1
    elif x < 2 + L + L:
        ans = all_pat_num(level-1) + 1 + pat(level - 1, x - 2 - L)
    else:
        ans = all_pat_num(level)
    return(ans)

print(pat(N, X))

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

lv_len=[1]
lv_pad=[1]

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

def solve(n,x):
  if n==0:
    return 1
  elif x==1:
    return 0
  else:
    if x <= lv_len[n]//2:
      return solve(n-1,x-1)
    elif x == lv_len[n]//2 +1:
      return 1 + solve(n-1,x-2)
    else:
      return lv_pad[n-1] + 1 + solve(n-1,x-(lv_len[n-1]+2))
    
print(solve(N,X))

Solution (Python):
def p_num(n,x):
    

    m = 2**(n+1)-1
    

    if n==0:
        return 1
    else:
        if x==1:
            return 0
        elif x==2*m-1:
            return m
            
        if x < m:
            
            return p_num(n-1, x-1)
        elif x > m:
            
            return (m-1)//2 + 1 + p_num(n-1, x-m)
        else:
            
            return (m-1)//2 + 1


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

print(p_num(n,x))

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






patty_num_map = {}
size_map = {}
patty_num_map[0] = 1
size_map[0] = 1
for i in range(1, 51):
    patty_num_map[i] = 1+patty_num_map[i-1]*2
    size_map[i] = 3+size_map[i-1]*2

L = N
patty_sum = 0
L1_map = {}
L1_map[0] = 0
L1_map[1] = 0
L1_map[2] = 1
L1_map[3] = 2
L1_map[4] = 3
L1_map[5] = 3
L1_map[6] = 3
for i in range(7, 10000):
    L1_map[i] = 3
while True:
    half = size_map[L]//2+1
    if L < 2:
        patty_sum += L1_map[X]
        break
    if X > half:
        patty_sum += patty_num_map[L-1]+1  
        
        X -= half
        L -= 1
    elif X < half:
        X -= 1  
        L -= 1
    else:  
        patty_sum += patty_num_map[L-1]+1
        break
print(patty_sum)

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

def left(total,x):
    if x > (total+1)//2:
        return x-(total+1)//2
    else:
        return x
def pati(n):
    return 2**(n+1)-1

n,x = map(int,input().split())
num = []
p = []
for i in range(n-1):
    num.append(total(i))
for i in range(n+1):
    p.append(pati(i))


one = ["B","P","P","P","B"]
num.reverse()
eat = [0 for i in range(n+1)]

ans = 0
for i in range(n-1):
    if x == total(n-i):
        eat[n-i] += 1
        x = 0
    elif x > (total(n-i)+1)//2:
        eat[n-i-1] += 1
        x = left(total(n-i),x)
        ans += 1
    elif x == (total(n-i)+1)//2:
        eat[n-i-1] += 1
        eat[0] += 1
        x = 0
    else:
        x -= 1

for i in range(len(eat)):
    ans += eat[i]*p[i]
if 2<=x<=4:
    ans += x-1
elif x == 5:
    ans += 3
print(ans)

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

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

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

def num_of_P_from_bottom(level, x):
    if level == 0:
        return 1

    prev_level_all = num_of_all[level-1]
    prev_level_P   = num_of_P[level-1]
    ret = 0

    if x <= 1:
        return 0
    elif x <= (2 + prev_level_all):
        if x == 2 + prev_level_all:
            ret += 1
        ret += num_of_P_from_bottom(level-1, x-1)
    else:
        ret += 1 + prev_level_P
        ret += num_of_P_from_bottom(level-1, x - (prev_level_all + 2))
    return ret

tmp = num_of_P_from_bottom(n, x)
print(tmp)

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

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

def count_p(level, X):
    if X == 0:
        return 0
    if X == burgersize[level]:
        return pnum[level]
    if level == 0:
        return 1
    Xmid = (burgersize[level] - 1) // 2 + 1
    if X < Xmid:
        return count_p(level - 1, X - 1)
    else:
        return pnum[level - 1] + 1 + count_p(level - 1, X - Xmid)

print(count_p(N, X))

Solution (Python):

N,X=[int(_) for _ in input().split()]
def countP(n):
    if n == 0:
        return 1
    elif n == 1:
        return 3
    else:
        return 1 + countP(n-1) * 2

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

def countPinBP(n,x):
    if x == 1:
        return 0
    if n == 0:
        if x == 1:
            return 0
        else:
            return 1
    elif n == 1:
        if x == 1:
            return 0
        elif x < 5:
            return x - 1
        else:
            return 3
    else:
        
        iH = 1 + countBP(n-1)
        if x <= iH:
            return countPinBP(n-1,x-1)
        elif x == iH + 1:
            return countP(n-1) + 1
        else:
            return countP(n-1) + 1 + countPinBP(n - 1, x - iH - 1)
print(countPinBP(N,X))

Solution (Python):
"""
P
1
B|P|P|P|B
0|1|1|1|0 3
B|BPPPB|P|BPPPB|B
0|3|1|3|0 7
a_1 = 1
a_n+1 = 2 * a_n + 3
b = 2b + 3 => b = -3
a_n + 3 = 4*2^(n-1)
a_n = 2^(n+2) - 3

b_1 = 1
b_n+1 = b_n * 2 + 1
c = 2c + 1 => c = -1
b_n + 1 = 2^n
b_n = 2^(n+1) - 1
"""


def check(n, x):
    if n == 0:
        return 0
    
    lower_n = 2 ** (n+1) - 3
    lower_pat = 2 ** n - 1
    if x == 1:
        return 0
    elif x == 1 + lower_n:
        return lower_pat
    elif x == 1 + lower_n + 1:
        return lower_pat + 1
    elif x == 1 + lower_n + 1 + lower_n:
        return lower_pat + 1 + lower_pat
    elif x == 1 + lower_n + 1 + lower_n + 1:
        return lower_pat + 1 + lower_pat
    elif 1 < x < 1 + lower_n:
        return check(n-1, x-1)
    elif 1 + lower_n + 1 <x< 1 + lower_n + 1 + lower_n:
        return lower_pat + 1 + check(n-1, x-1-lower_n-1)

N, X = [int(s) for s in input().split()]
print(check(N, X))

Solution (Python):
nx = list(map(int, input().split()))
n = nx[0]
x = nx[1]
p = 0
for i in range(n):
    l_thick = 2 ** (n - i + 1) - 3
    if x == 1:
        break
    elif x <= l_thick:
        x = x - 1
    elif x == l_thick + 1 :
        p += 2 ** (n - i) - 1
        break
    elif x <= l_thick * 2 + 1:
        x = x - l_thick - 2
        p += 2 ** (n - i)
    else:
        p += 2 * (2 ** (n - i) - 1) + 1
        break
print(p)

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


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


print(solve(N, X))

Solution (Python):
def dfs(lft, rgt, x, L):
    if x < lft: return 0
    if rgt <= x: return numPs[L]
    mid = (lft + rgt) // 2
    ans = 1 if mid <= x else 0
    ans += dfs(lft + 1, mid - 1, x, L - 1)
    ans += dfs(mid + 1, rgt - 1, x, L - 1)
    return ans

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

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

print(dfs(1, As[N], X, N))

Solution (Python):
N, X = [int(i) for i in input().split(' ')]

def f(n):
    return 4 * pow(2, n) - 3
def g(n):
    return pow(2, n+1) - 1

def ss2(k, n):
    if n == 0:
        return 1
    nn = f(n)
    cc = (nn//2) + 1
    if k == 1:
        return 0
    if k >= nn:
        return g(n) 
    elif k == cc:
        return g(n-1) + 1  
    elif k > cc:
        return g(n-1) + 1 + ss2(k-cc, n-1)
    elif k < cc:
        return ss2(k-1, n-1)

print(ss2(X, N))

Solution (Python):
a,b= map(int,input().split())

l = 1

c = [1]
d = [1]

for i in range(50):
	c.append(2*c[-1]+3)
	d.append(2*d[-1]+1)
k = 0
while True:
	if a == 0:
		k += 1
		break
	elif b==1:
		break
	elif c[a] // 2 == b:
		k += d[a-1]
		break
	elif c[a] // 2 > b:
		a -= 1
		b -= 1
	elif c[a] // 2 + 1 == b:
		k += 1 + d[a-1]
		break
	elif c[a] // 2 + 1 < b and c[a] != b:
		a -= 1
		k += d[a]+1
		b -= c[a]+2
	else:
		k += d[a]
		break


print(k)

Solution (Python):

from sys import stdin

def solve():
    n, x = map(int, stdin.readline().split())
    items = []
    items.append([1,1])
    for i in range(1,n+1):
        items.append([items[-1][0]*2+3, items[-1][1]*2+1])
    
    if x<=n:
        print(0)
        return
    
    ans = 0
    p = n
    while p and x:
        half = (items[p][0]+1)//2
        if x>=half:
            ans += items[p-1][1] + 1
            x -= half
        else:
            x -= 1
        p -= 1

    if x:
        ans += 1
    print(ans)

solve()

Solution (Python):
def patti(level):
    return 2 ** (level + 1) - 1


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


def get_ans(level, x, num_patti):
    if level == 0:
        return num_patti + x

    if x == 1 or x == 0:
        return num_patti
    elif x < 1 + burger(level - 1):
        x -= 1
        return get_ans(level - 1, x, num_patti)
    elif x == 1 + burger(level - 1):
        return patti(level - 1) + num_patti
    elif x == 1 + burger(level - 1) + 1:
        return patti(level - 1) + num_patti + 1
    elif x < 1 + burger(level - 1) + 1 + burger(level - 1):
        x -= 1 + burger(level - 1) + 1
        num_patti += 1 + patti(level - 1)
        tmp = get_ans(level - 1, x, num_patti)
        return tmp
    else:
        return num_patti + patti(level - 1) * 2 + 1


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

print(get_ans(n, x, 0))

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

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

print(p(n, x))