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.



Sample input:
2 7


Sample output:
4

Submission status: Accepted

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


def length(n):
    return 4*2**n - 3


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


print(func(N, X))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
dp={}
def f(n,x):
    if (n,x) in dp:
        return dp[(n,x)]
    elif (n,x)==(0,1):
        return 1
    else:
        if x==1:
            answer=0
            return answer
        elif 2<=x<=2**(n+1)-2:
            answer=f(n-1,x-1)
            return answer
        elif x==2**(n+1)-1:
            answer=f(n-1,2**(n+1)-3)+1
            return answer
        elif 2**(n+1)<=x<=2**(n+2)-4:
            answer=f(n-1,2**(n+1)-3)+f(n-1,x-2**(n+1)+1)+1
            return answer
        else:
            answer=2*f(n-1,2**(n+1)-3)+1
            return answer
print(f(N,X))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
dp={}
def f(n,x):
    if (n,x) in dp:
        return dp[(n,x)]
    elif (n,x)==(0,1):
        return 1
    else:
        if x==1:
            answer=0
            dp[(n,x)]=answer
            return answer
        elif 2<=x<=2**(n+1)-2:
            answer=f(n-1,x-1)
            dp[(n,x)]=answer
            return answer
        elif x==2**(n+1)-1:
            answer=f(n-1,2**(n+1)-3)+1
            dp[(n,x)]=answer
            return answer
        elif 2**(n+1)<=x<=2**(n+2)-4:
            answer=f(n-1,2**(n+1)-3)+f(n-1,x-2**(n+1)+1)+1
            dp[(n,x)]=answer
            return answer
        else:
            answer=2*f(n-1,2**(n+1)-3)+1
            dp[(n,x)]=answer
            return answer
print(f(N,X))

Submission status: Accepted

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

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

def B(n): return 2**(n+1) - 1 # returns number of buns in level n


def eat(neat,level):

    if level == 0:
        return 1 if neat > 0 else 0

    elif neat < 2:
        return 0

    t = thickness[level]
    center = t//2 + 1

    if neat == t:
        return B(level)

    elif neat < center:
        return eat(neat-1, level-1)

    else: # neat >= center
        return 1 + B(level-1) + eat(neat - center, level-1)

print(eat(X, N))

Submission status: Accepted

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

def eat(l,x):
    if x==0:
        return 0
    if l==0:
        return 1
    if x<b[l-1]+2:
        ans=eat(l-1,x-1)
    else:
        ans=p[l-1]+1+eat(l-1,x-2-b[l-1])
    return ans
print(eat(n,x))

Submission status: Accepted

Solution code:
N,X = map(int, input().split())
num, p = [1], [1]
index = 1
while N >= index:
    num.append(2*num[-1] + 3)
    p.append(2*p[-1] + 1)
    index +=1

def ans(n, x):
    if n == 0:
        return 1 if x > 0 else 0
    if x <= num[n-1]+1:
        return ans(n-1, x-1)
    else:
        return p[n-1] +1+ ans(n-1, x-2-num[n-1])

print(ans(N, X))

Submission status: Accepted

Solution code:
import sys

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


def p_num(l):
    """レベルlバーガーに含まれるパティの数を返す
    """
    return 2**(l+1)-1


def l_num(l):
    """レベルlバーガーに含まれる層の数
    """
    return 2**(l+2)-3


def p_num_l(level, x):
    """レベルlevelバーガーの1, 2, ...x層までのうちのパティーの数を返す
    """
    if level == 0:
        return 1
    if x == 1:
        return 0
    elif x == 2**(level+1)-1:
        return p_num(level-1)+1
    elif x == 2**(level**2)-3:
        return 2*p_num(level-1)+1
    elif x < 2**(level+1)-1:
        return p_num_l(level-1, x-1)
    else:
        return p_num(level-1)+1+p_num_l(level-1, x-2-l_num(level-1))


print(p_num_l(N, X))

Submission status: Accepted

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

def get_size(level):
    return (1 << (level+2)) - 3

def get_patty(level):
    return (1 << (level+1)) - 1

ans = 0
while X > 0:
    if get_size(N) > X:
        X -= 1
        N -= 1
    else:
        X -= get_size(N)
        ans += get_patty(N)
        if X > 0:
            ans += 1
            X -= 1
print(ans)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

n_sum= X
answer = [0]
def saiki(layer,n_sum,sum_p):
    # print(layer,n_sum,sum_p)
    # if layer == 0:
    #     answer[0] = sum_p
    #     return
    if n_sum == 0:
        answer[0] = sum_p
        return 
    if layer == 1:
        if n_sum == 1:
            answer[0] = sum_p
        elif n_sum == 2:
            answer[0] = sum_p+1
        elif n_sum ==3:
            answer[0] = sum_p+2
        else:
            answer[0] = sum_p+3
        return

    ##現layerの合計を計算
    layer_sum = 2**(layer+2)-3
    ##前のlayerの合計を計算
    pre_layer_sum = 2**(layer+1)-3
    pre_p_sum = 2**(layer)-1
    #もし左側
    if n_sum  < layer_sum //2 +1 :
        # print("left")
        n_sum -= 1
        saiki(layer-1,n_sum,sum_p)
    
    else:
        # print("right")
        n_sum -= (pre_layer_sum+2)
        sum_p += (1+pre_p_sum)
        saiki(layer-1,n_sum,sum_p)

saiki(N,X,0)

print(answer[0])

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def _level(n):
	if n == 0:
		return 1
	else:
		return 3 + 2 * level(n-1)

def _eat(n, x):
	if n == 0:
		return 1 if x > 0 else 0
	if x <= 1:
		return 0
	if x <= 1 + level(n-1):
		return eat(n-1, x-1)
	if x == 1 + level(n-1) + 1:
		return eat(n-1, level(n-1)) + 1
	if x <= 1 + level(n-1) + 1 + level(n-1):
		return eat(n-1, level(n-1)) + 1 + eat(n-1, x - (1 + level(n-1) + 1))
	else:
		return eat(n-1, level(n-1)) + 1 + eat(n-1, level(n-1))

store = {}

def level(n):
	if n not in store:
		store[n] = _level(n)
	return store[n]

def eat(n, x):
	if (n, x) not in store:
		store[(n, x)] = _eat(n, x)
	return store[(n, x)]


print(eat(*map(int, input().split())))

Submission status: Accepted

Solution code:
def patty(n,x):
    if x == 0:
        return 0
    elif n == 0:
        #print(n,x,1)
        return 1
    elif x == 1 and n > 0:
        return 0
    num = 2 ** (n+2) - 3
    pre_num = 2 ** (n+1) - 3
    if x == num:
        #print(n,x,2 * patty(n-1,pre_num) + 1)
        return 2 * patty(n-1,pre_num) + 1
    elif x > pre_num + 1:
        #print(n,x,patty(n-1,pre_num) + 1 + patty(n-1,x - pre_num - 2))
        return patty(n-1,pre_num) + 1 + patty(n-1,x - pre_num - 2)
    elif x == pre_num + 1:
        #print(n,x,patty(n-1,pre_num) + 1)
        return patty(n-1,pre_num)
    else:
        #print(n,x,patty(n-1,x-1))
        return patty(n-1,x-1)

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

print(patty(n,x))

Submission status: Accepted

Solution code:
import sys
import collections
ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
nsl = lambda: map(str, sys.stdin.readline().split())

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


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

print(f(N, X))

Submission status: Accepted

Solution code:
def solve(string):
    n, x = map(int, string.split(" "))
    t = ["P"]
    for _ in range(10):
        t.append("B{}P{}B".format(t[-1], t[-1]))
    l, p = [1], [1]
    for _ in range(n):
        l.append(2 * l[-1] + 3)
        p.append(2 * p[-1] + 1)

    def rec(i, x):
        if i <= 10:
            return t[i][:x].count("P")
        if x > l[i - 1] + 2:
            return p[i - 1] + 1 + rec(i - 1, x - l[i - 1] - 2)
        elif x == l[i - 1] + 2:
            return p[i - 1] + 1
        else:
            return rec(i - 1, x - 1)

    return str(rec(n, x))


if __name__ == '__main__':
    print(solve(input()))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
def an(n):
    return 2**(n+1)-1
def bn(n):
    return 2**(n+2)-3
ans=0
while(N+1):
    if X==0:

        print(ans)
        quit()
    if X==bn(N):
        ans+=an(N)
        print(ans)
        quit()
    if X<=(bn(N)-1)/2:
        X-=1
        N-=1
    elif X==(bn(N)-1)/2+1:
        ans+=an(N-1)+1
        print(ans)
        quit()
    else:
        X=X-(bn(N-1)+2)
        ans+=an(N-1)+1
        N-=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def POW(x, y):
    if y == 0:
        return 1
    elif y == 1:
        return x
    elif y % 2 == 0:
        return POW(x, y // 2) ** 2 % MOD
    else:
        return POW(x, y // 2) ** 2 * x % MOD
def mod_factorial(x, y): return x * POW(y, MOD - 2) % MOD
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()
from collections import Counter

patis = [INF] * 51
layers = [INF] * 51
patis[0] = layers[0] = 1

def calc_layers(n):
    if layers[n] == INF:
        layers[n] = 3 + calc_layers(n - 1) * 2
    return layers[n]
calc_layers(50)

def calc_patis(n):
    if patis[n] == INF:
        patis[n] = 1 + calc_patis(n - 1) * 2
    return patis[n]
calc_patis(50)

def dfs(n, x):
    if layers[n] <= x:
        return patis[n], x - layers[n]
    ret = 0
    x -= 1
    if x <= 0:
        return ret, 0
    r, x = dfs(n - 1, x)
    ret += r
    if x <= 0:
        return ret, 0
    x -= 1
    ret += 1
    if x <= 0:
        return ret, 0
    r, x = dfs(n - 1, x)
    ret += r
    if x <= 0:
        return ret, 0
    x -= 1
    ret += 1
    return ret, x

def main():
    N, X = LI()
    ans, _ = dfs(N, X)
    return ans

print(main())

Submission status: Accepted

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

l1 = 'BPPPB'

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

dp = [-1]*51

def solve(n, x):
    if n == 0:
        return 1
    l_num = L[n]
    temp = 0
    if dp[n-1]==-1:
        temp = solve(n-1, L[n-1])
        dp[n-1] = temp
    else:
        temp = dp[n-1]

    if x == l_num//2+1:
        return temp+1
    elif n < x < l_num//2+1:
        return solve(n-1, x-1)
    elif x > l_num//2+1:
        # if n==3:
        #     print(x-l_num//2)
        return temp+1 +\
                solve(n-1, x-l_num//2-1)
    elif x <= n:
        return 0

print(solve(N,X))

Submission status: Accepted

Solution code:
import sys

nx = input().split()
n = int(nx[0])
x = int(nx[1])
count = 0


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

pcountlist = []
for i in range(n + 1):
    if i == 0:
        pcountlist.append(1)
    else:
        pcountlist.append(pcountlist[-1] * 2 + 1)


def incr_count(nn, xx):
    global count

    if nn == 0:
        if xx > 0:
            count += 1
        return

    if xx <= 1:
        pass
    if 1 < xx and xx <= lenlist[nn] // 2:
        incr_count(nn - 1, xx - 1)
    if lenlist[nn] // 2 < xx:
        count += pcountlist[nn - 1]
        count += 1
        incr_count(nn - 1, xx - lenlist[nn] // 2 - 1)


incr_count(n, x)
print(count)

Submission status: Accepted

Solution code:
l = [1]
p = [1]
N, X = map(int, input().split())
for i in range(N):
    l.append(l[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


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

print(calc(N, X))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

height=[-1]*51
niku=[-1]*51
height[0]=1
niku[0]=1

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

def rec(l, x):
    if x==1:
        if l==0:
            return 1
        else:
            return 0
    
    if x < 1+height[l-1]+1:
        return rec(l-1, x-1)
    elif x == 1+height[l-1]+1:
        return 1 + niku[l-1]
    elif x <= height[l] - 1:
        return niku[l-1] + 1 + rec(l-1, x-height[l-1]-2)
    else:
        return 2*niku[l-1]+1
print(rec(N, X))

Submission status: Accepted

Solution code:

ans = 0
def count_ans(level, index, len_dic, p_dic):
    global ans
    if level == 0:
        ans += 1
    else:
        if index == 0:
            pass
        elif index == len_dic[level] // 2:
            ans += 1
            ans += p_dic[level - 1]
        elif index == len_dic[level] - 1:
            ans += p_dic[level]
        elif index > len_dic[level] // 2:
            ans += p_dic[level - 1] + 1
            index_next = index - len_dic[level - 1] - 2
            count_ans(level - 1, index_next, len_dic, p_dic)
        else:
            index_next = index - 1
            count_ans(level - 1, index_next, len_dic, p_dic)


def get_len_dic(level):
    len_dic = [1]
    for i in range(level):
        len_dic.append(len_dic[-1] * 2 + 3)
    return len_dic

def get_p_dic(level):
    p_dic = [1]
    for i in range(level):
        p_dic.append(p_dic[-1] * 2 + 1)
    return p_dic

def main():
    global ans
    level, eat_num = map(int, input().split())
    len_dic = get_len_dic(level)
    p_dic = get_p_dic(level)
    count_ans(level, eat_num - 1, len_dic, p_dic)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache

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


@lru_cache(maxsize=None)
def count_patti(level, index):
    """
    左から index 番目までのパティの数
    :param level:
    :param index:
    :return:
    """
    if level == 0:
        return 1
    if index == 0:
        return 0
    if 1 <= index < (sizes[level] - 1) / 2:
        return count_patti(level - 1, index - 1)
    if index == (sizes[level] - 1) / 2:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1
    if (sizes[level] - 1) / 2 < index < sizes[level] - 1:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1 + \
               count_patti(level - 1, index - (sizes[level] - 1) / 2 - 1)
    else:
        return count_patti(level - 1, sizes[level - 1] - 1) + 1 + \
               count_patti(level - 1, sizes[level - 1] - 1)


print(count_patti(n, x - 1))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float('inf')
MOD = 10**9+7
dy = [0,1,0,-1]
dx = [1,0,-1,0]
ddy = [0,1,1,1,0,-1,-1,-1]
ddx = [1,1,0,-1,-1,-1,0,1]

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

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

print(f(n,x))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

def ln(n: int):
    return pow(2,n+1) - 3

def pn(n: int):
    return pow(2,n) - 1

def calc(N: int, X: int):
    if N == 0:
        return 0
    if N == 1:
        return 1
    n1 = ln(N - 1)
    if X == 1:
        return 0
    elif X <= 1 + n1:
        return calc(N-1,X-1)
    elif X == 2 + n1:
        return 1 + calc(N-1,X-1)
    elif X <= 2 + 2*n1:
        return 1 + pn(N-1) + calc(N-1,X-2-n1)
    else:
        return 1 + pn(N-1)*2

def solve(N: int, X: int):
    print(calc(N + 1,X))
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


@functools.lru_cache(None)
def hight(n):
    if n == 0:
        return 1
    else:
        return 2*hight(n-1)+3


@functools.lru_cache(None)
def paty(n):
    if n == 0:
        return 1
    else:
        return 2*paty(n-1)+1


def rec(n, x):
    # print(n, x)
    if n == 0:
        if x == 0:
            return 0
        else:
            return 1

    if x == 0:
        return 0
    elif x == 1:
        return 0
    elif x < hight(n-1)+2:
        return rec(n-1, x-1)
    elif x == hight(n-1)+2:
        return paty(n-1) + 1
    else:
        # print(paty(n-1)+1)
        return paty(n-1)+1 + rec(n-1, x-(hight(n-1)+2))


def solve(N: int, X: int):
    print(rec(N, X))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


@functools.lru_cache(None)
def hight(n):
    return 2**(n+2)-3


@functools.lru_cache(None)
def paty(n):
    return 2**(n+1)-1


def rec(n, x):
    # print(n, x)
    if n == 0:
        if x == 0:
            return 0
        else:
            return 1

    if x == 0:
        return 0
    elif x == 1:
        return 0
    elif x < hight(n-1)+2:
        return rec(n-1, x-1)
    elif x == hight(n-1)+2:
        return paty(n-1) + 1
    else:
        # print(paty(n-1)+1)
        return paty(n-1)+1 + rec(n-1, x-(hight(n-1)+2))


def solve(N: int, X: int):
    print(rec(N, X))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

burger = [1 for i in range(52)]
for i in range(1,52):
    burger[i] = burger[i-1]*2+3
patty = [1 for i in range(52)]
for i in range(1,52):
    patty[i] = patty[i-1]*2 + 1
def solve(L,X):
    if X == 0:
        return 0
    if burger[L] == X:
        return patty[L]
    elif (burger[L]-1)//2 + 1 == X:
        return patty[L-1] + 1
    elif (burger[L]-1)//2 + 1 > X:
        return solve(L-1,X-1)
    elif (burger[L]-1)//2 + 1 < X:
        return patty[L-1] + 1 + solve(L-1,X-burger[L-1]-2)

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

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
def bisearch(n, l):
    half = (2**(n+2)-3) // 2
    return 0 if l <= 0 else 2**n + bisearch(n-1, min(l - 1 - half, half)) if half < l else bisearch(n-1, l-1)
print(bisearch(N, X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
def bisearch(n, l):
    if l <= 0:
        return 0
    half = (2**(n+2)-3) // 2
    if half < l:
        return 2**(n) + bisearch(n-1, min(l - 1 - half, half))
    else:
        return bisearch(n-1, l-1)

print(bisearch(N, X))

Submission status: Accepted

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

layers={0:1}
def layers_of_level(n):
    if n in layers:
        return layers[n]
    layers[n] = 2*layers_of_level(n-1)+3
    return layers[n]

def how_many_putty(n,x):
    if n==0 and x==1:
        return 1
    if n==layers_of_level(n):
        return 2**(n+1)-1

    total_layers = layers_of_level(n)
    if x==1:
        return 0
    if x <= 1+layers_of_level(n-1):
        return how_many_putty(n-1, x-1)
    if x == 1+layers_of_level(n-1)+1:
        return how_many_putty(n-1, x-2)+1
    if x <= 1+2*layers_of_level(n-1)+1:
        return how_many_putty(n-1,layers_of_level(n-1))+1+ how_many_putty(n-1,x-layers_of_level(n-1)-2)
    else:
        return 2*how_many_putty(n-1,layers_of_level(n-1))+1

print(how_many_putty(N,X))

Submission status: Accepted

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

a=[0]*(n+1)
a[0]=1
p=[0]*(n+1)
p[0]=1

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


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

Submission status: Accepted

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

a=[0]*(n+1)
a[0]=1
p=[0]*(n+1)
p[0]=1

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


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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

print(f(N, X))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def io_generator():
	return input()

#+++++++++++++++++++

def n_pat(a_n):
	return 2**a_n - 1
	
def n_size(a_n):
	return 4 * (2** (a_n -1))- 3
	
def get_size(n,x):
	if x == 0:
		return 0
	elif x==1:
		return 0
	elif x < 1 + n_size(n):
		return get_size(n-1, x -1)
	elif x == 1 + n_size(n):
		return n_pat(n)
	elif x == 1 + n_size(n) + 1:
		return n_pat(n) + 1
	elif x < 1 + n_size(n) +1 + n_size(n):
		offset=2 + n_size(n)
		return n_pat(n)+1+get_size(n-1, x - offset)
	else:#if x == 1+n_size(n)+1+n_size(n):
		return n_pat(n)+1+n_pat(n)

def main(io):
	n,x= map(int, io().split())
	return get_size(n,x)
	#for i in range(1,51):
	#	print(n_pat(i),n_size(i))
	#return str(a+b+c) + " " + s

#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

Submission status: Accepted

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
a = [2**(i+2) - 3 for i in range(N+1)]  # 層の数
p = [2**(i+1) - 1 for i in range(N+1)]  # パティの数
def f(N, X):
    if N == 0:
        return 1 if X > 0 else 0
    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))

Submission status: Accepted

Solution code:
nums = [0] * 51
ps = [0] * 51


def calc(l, x):
    global nums, ps

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

    if x == 1:
        return 0
    elif x <= 1 + nums[l - 1]:
        return calc(l - 1, x - 1)
    elif x == 2 + nums[l - 1]:
        return ps[l - 1] + 1
    elif x <= 2 + 2 * nums[l - 1]:
        return ps[l - 1] + 1 + calc(l - 1, x - 2 - nums[l - 1])
    else:
        return ps[l]


def main():
    global nums, ps
    nums[0] = 1
    ps[0] = 1
    for i in range(len(nums)):
        if i == 0:
            continue
        nums[i] = 2 * nums[i - 1] + 3
        ps[i] = 2 * ps[i - 1] + 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
p=[0]*(N+1)
num=[0]*(N+1)
for i in range(N+1):
    p[i] = 2**(i+1)-1
for i in range(N+1):
    num[i] = 2**(i+2)-3
def f(L,x):
    if L == 0:
        return 0 if x<=0 else 1
    elif x < ((2**(L+2)-4)//2+1):
        return f(L-1,x-1)
    else:
        return p[L-1]+1+f(L-1,x-2-num[L-1])

print(f(N,X))

Submission status: Accepted

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

def pati(l, n):
    if n == 0:
        return 0
    elif l == 0:
        return 1
    elif n == 1:
        return 0
    elif 2 <= n <= maisuu[l] // 2:
        return pati(l - 1, n - 1)
    else:
        return pati(l - 1, n - maisuu[l - 1] - 2) + 1 + patimaisuu[l - 1]

print(pati(N, X))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, X: int):
    total = [0] * (N + 1)
    p = [0] * (N + 1)
    total[0] = 1
    p[0] = 1
    for i in range(1, N + 1):
        total[i] = total[i - 1] * 2 + 3
        p[i] = p[i - 1] * 2 + 1
    def rec(idx, x):
        if x <= 0:
            return 0
        if x >= total[idx] - idx:
            return p[idx]
        elif x <= total[idx] // 2:
            return rec(idx - 1, x - 1)
        else:
            rest = x - (total[idx] // 2 + 1)
            ret = p[idx - 1] + 1 + rec(idx - 1, rest)
        return ret
    ret = rec(N, X)
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def f(level,x):
    if level==0: return x

    if x in [1,0]:
        return 0
    elif x==b[level][0]:
        return b[level][1]
    elif 2<=x<b[level-1][0]+2:
        return f(level-1,x-1)
    elif x==b[level-1][0]+2:
        return b[level-1][1]+1
    elif b[level-1][0]+2<x<b[level][0]:
        return b[level-1][1]+1+f( level-1, x-(b[level-1][0]+2))

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

print(f(N,X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
lenburger = [1]
lenputty = [1]
for i in range(N):
    lenburger.append(lenburger[i]*2+3)
    lenputty.append(lenputty[i]*2+1)
def burger(level, X):
    if level == 0:
        return 1
    elif X == 1:
        return 0
    elif X <= 1 + lenburger[level-1]:
        return burger(level-1, X-1)

    elif X == 2 + lenburger[level-1]:
        return 1 + lenputty[level-1]

    elif X <= 2 + lenburger[level-1]*2:
        return 1 + lenputty[level-1] + burger(level-1, X-2-lenburger[level-1])

    else:
        return lenputty[level]
print(burger(N, X))

Submission status: Accepted

Solution code:
sou = lambda n: 2 ** (n + 2) - 3
ptn = lambda n: 2 ** (n + 1) - 1


def pate(lv, x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    else:
        for i in range(lv + 1):
            if x < lv - i + sou(i):
                i -= 1
                return ptn(i) + 1 + pate(i, x - (lv - i + sou(i) + 1))
        else:
            return ptn(lv)


lv, x = map(int, input().split())
print(pate(lv, x))

Submission status: Accepted

Solution code:
sou = lambda n: 2 ** (n + 2) - 3
ptn = lambda n: 2 ** (n + 1) - 1


def pate(lv, x):
    if x == 0:
        return 0
    if x < 0:
        return -1
    else:
        for i in range(lv + 1):
            if x < lv - i + sou(i):
                i -= 1
                re = ptn(i) + 1 + pate(i, x - (lv - i + sou(i) + 1))
                return re
        else:
            return ptn(lv)


lv, x = map(int, input().split())
print(pate(lv, x))

Submission status: Accepted

Solution code:
N,X = [int(i) for i in input().split()]
ans = 0
while N > 0:
    if X >= 2**(N+2) - 4: #N=2 12 N=1 4
        ans += 2**(N+1) - 1
        break
    
    elif X > 2**(N+1) - 1: #N=2 7
        ans += 2**N
        X -= 2**(N+1) - 1
        
    elif X == 2**(N+1) - 1: #N=2 7
        ans += 2**N
        break
    
    elif X == 2**(N+1) - 2: #N=2 6
        ans += 2**N - 1
        break
    
    elif X > 1:
        X -= 1
        
    else:
        break
    N -= 1
print(ans)