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())
hight, paty = [0]*51, [0]*51
hight[0] = 1
paty[0] = 1

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

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

	elif x <= (hight[n-1]+1):
		return f(n-1, x-1)
	else:
		return paty[n-1] + 1 + f(n-1, x-hight[n-1]-2)

print(f(N, X))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def func(num, pos):
    if num == 1:
        return 1
    elif pos == 1:
        return 0
    elif 1 < pos < (num + 2 - 1) // 2:
        return func((num - 3) // 2, pos - 1)
    elif pos == (num + 2 - 1) // 2:
        return func((num - 3) // 2, (num - 3) // 2) + 1
    elif (num + 2 - 1) // 2 < pos < num:
        return func((num - 3) // 2, (num - 3) // 2) + func((num - 3) // 2, pos - (num - 3) // 2 - 2) + 1
    elif pos == num:
        return func((num - 3) // 2, (num - 3) // 2) * 2 + 1


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, x = list(map(int, input().rstrip('\n').split()))
    t = 1
    for i in range(n):
        t = t * 2 + 3
    print(func(t, x))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
from sys import stdin
N, X = [int(x) for x in stdin.readline().rstrip().split()]

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


def solve(n, x):
    if n == 0 and x == 1:
        return 1
    elif x == 1:
        return 0
    elif 1 < x <= 1+heights[n-1]:
        return solve(n-1, x-1)
    elif x == 2+heights[n-1]:
        return 1+putties[n-1]
    elif 2+heights[n-1] < x <= 2+2*heights[n-1]:
        return putties[n-1]+1+solve(n-1,x-2-heights[n-1]) 
    elif x == 3+2*heights[n-1]:
        return 2*putties[n-1]+1
print(solve(N, X))

Submission status: Accepted

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

BP = [1]
P = [1]

for i in range(n):
  BP.append(BP[i]*2+3)
  P.append(P[i]*2+1)
  
def check_P_num(n, x):
  
  if n==0:
    return 1
  
  if x==BP[n]:
    return(P[n])
  elif x==1:
    return(0)
  elif x == BP[n-1]+2:
    return(P[n-1]+1)
  elif x <= BP[n-1]+1:
    return(check_P_num(n-1, x-1))
  else:
    return(check_P_num(n-1, x-BP[n-1]-2)+P[n-1]+1)
  
  
print(check_P_num(n, x))

Submission status: Accepted

Solution code:
"""
22.40.00

"""

N,X = map(int, input().split())
# 層の数 : 2**(N+2) - 3
# パティの数 : 2**(N+1) - 1
# 肉の数 : 2**(N+1) - 2
l = N
cnt = 0
while l >= 0:
    n_all = 2**(l+2) - 3
    p_all = 2**(l+1) - 1
    if l == 0:
        cnt += 1
    if X == 1:
        break
    elif X == n_all:
        cnt += p_all
        break
    elif X == (n_all+1)//2:
        cnt += (p_all+1) // 2
        break
    elif 1 < X < (n_all+1)//2:
        X -= 1
    elif (n_all+1)//2 < X < n_all:
        X -= (n_all+1)//2
        cnt += 2**l
    l -= 1

print(cnt)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
#バーガーは2*cnt+3、パティは2*cnt+1
#レベルNバーガー&パティの総数リスト　indexは[N]
numB = [1]
numP = [1]
for i in range(50):
    numB.append(numB[i]*2+3)
    numP.append(numP[i]*2+1)
#二分探索の作成
L = 0; R = numB[N]+1
K = N   #Kは今調べているバーガー
ans = 0
while K>0:
    Mid = (L+R)//2
    if X == L+1:
        break
    if L+2 <= X <= Mid-1:
        K -= 1
        L += 1; R = Mid
        continue
    if X == Mid:
        ans += numP[K-1]+1
        break
    if Mid+1 <= X <= R-2:
        ans += numP[K-1]+1
        K -= 1
        L = Mid; R -= 1
        continue
    if X == R-1:
        ans += numP[K]
        break
else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
#バーガーは2*cnt+3、パティは2*cnt+1
#レベルNバーガー&パティの総数リスト　indexは[N-1]
numB = [1]
numP = [1]
for i in range(50):
    numB.append(numB[i]*2+3)
    numP.append(numP[i]*2+1)
#二分探索の作成
L = 0; R = numB[N]+1
K = N   #Kは今調べているバーガー
ans = 0
while K>0:
    Mid = (L+R)//2
    if X == L+1:
        break
    if L+2 <= X <= Mid-1:
        K -= 1
        L += 1; R = Mid
        continue
    if X == Mid:
        ans += numP[K-1]+1
        break
    if Mid+1 <= X <= R-2:
        ans += numP[K-1]+1
        K -= 1
        L = Mid; R -= 1
        continue
    if X == R-1:
        ans += numP[K]
        break
else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
ans = 0
while N >= 0:
    if N == 0:
        ans += 1
        break
    s = 2 ** (N + 2) - 3
    # V = 2 ** (N + 1) - 1
    if X == 1:
        # ans += 1
        break
    elif X < (s + 1) // 2:
        X -= 1
    elif X == (s + 1) // 2:
        ans += 2 ** N
        break
    elif X > (s + 1) // 2:
        ans += 2 ** N
        X -= (s + 1) // 2
    elif X == s:
        ans += 2 ** (N + 1) - 1
        break
    N -= 1
print(ans)

Submission status: Accepted

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

a = [1]
p = [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))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
B = [1]
P = [1]

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

    
def f(N, X):
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 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:
import sys
n, x = map(int, input().split())
ans = 0
layer = [1 for _ in range(n+1)]
patty = [1 for _ in range(n+1)]
for i in range(1,n+1):
    layer[i] = 2*layer[i-1]+3
    patty[i] = 2*patty[i-1]+1
def eat(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    elif x <= 1+layer[n-1]:
        return eat(n-1, x-1)
    elif x == 2+layer[n-1]:
        return patty[n-1]+1
    elif x <= 2+2*layer[n-1]:
        return patty[n-1]+1+eat(n-1, x-2-layer[n-1])
    else:
        return 2*patty[n-1]+1
ans = eat(n, x)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
p, q = [1] + [0] * n, [1] + [0] * n

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

def rec(i, x):
    if i == 0: return 1 if x >= 1 else 0
    mid = q[i-1] + 2
    if x < mid:
        return rec(i-1, x-1)
    else:
        return p[i-1] + 1 + rec(i-1, x-mid)

print(rec(n, x))

Submission status: Accepted

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if pattiesCount(i) != p[i]:
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat >= 1)
    both = bothCount(level - 1)
    patties = pattiesCount(level - 1)
    if eat == both + 2:
        return 1 + patties
    if eat > both + 1:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Accepted

Solution code:
import os, sys, re, math

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

memo_length = [0 for i in range(51)]
memo_patties = [0 for i in range(51)]
memo_length[0] = 1
memo_patties[0] = 1

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

def doit(level,x):
    if x == 0:
        return 0
    if x >= memo_length[level]:
        return memo_patties[level]

    tmp = memo_length[level-1]
    ret = 0

    if x >= 1:
        ret += doit(level-1, x-1)
    if x >= tmp + 2:
        ret += 1
        ret += doit(level-1, x-tmp-2)

    return ret

print(doit(N,X))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split(' ')))
lens = {0: 1}
for i in range(1, 51):
  lens[i] = lens[i-1] * 2 + 3

memo = {}
def sumP(level, index):
  key = (level, index)
  if key in memo:
    return memo[key]
  if level == 0:                       # |P or P|
      memo[key] = int(index == 1)
  elif index < lens[level] // 2 + 1:   # |Bxxxxxxx|xxxxxPxxxxxxxxxxB
    memo[key] = sumP(level-1, index-1)
  elif index <= lens[level] // 2 + 1:  # |BxxxxxxxxxxxxP|xxxxxxxxxxB
    memo[key] = 1 + sumP(level-1, lens[level-1])
  else:                                # |BxxxxxxxxxxxxPxxxxxxxx|xxB
    memo[key] = sumP(level-1, lens[level-1]) + 1 + sumP(level-1, min(lens[level-1], index-lens[level-1]-2))
  return memo[key]

print(sumP(n, k))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split(' ')))
lens = {0: 1}
for i in range(1, 51):
  lens[i] = lens[i-1] * 2 + 3
memo = {}
def sumP(level, index):
  key = (level, index)
  if key in memo:
    return memo[key]
  if level == 0:
    if index == 1:
      memo[key] = 1
    else:
      memo[key] = 0
  elif index < lens[level] // 2 + 1:  # レベル一つ下の奴の一部分のみ
    memo[key] = sumP(level-1, index-1)
  elif index == lens[level] // 2 + 1:  # ど真ん中のPを入れて一つ下全部(index-1は左端のB)
    memo[key] = 1 + sumP(level-1, lens[level-1])
  else: # レベル一つ下の奴の丸々1つ + P + レベル一つ下の奴の一部分もしくは全部, minは最後のBを捨てるため
    memo[key] = sumP(level-1, lens[level-1]) + 1 + sumP(level-1, min(lens[level-1], index-lens[level-1]-2))
  return memo[key]
 
print(sumP(n, k))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split(' ')))
lens = {}
lens[0] = 1
for i in range(1, 51):
  lens[i] = lens[i-1] * 2 + 3
memo = {}
def sumP(level, index):
  key = (level, index)
  if key in memo:
    return memo[key]
  if level == 0:
    if index == 1:
      memo[key] = 1
    else:
      memo[key] = 0
  elif index < lens[level] // 2 + 1:  # レベル一つ下の奴の一部分のみ
    memo[key] = sumP(level-1, index-1)
  elif index == lens[level] // 2 + 1:  # ど真ん中のPを入れて一つ下全部(index-1は左端のB)
    memo[key] = 1 + sumP(level-1, lens[level-1])
  else: # レベル一つ下の奴の丸々1つ + P + レベル一つ下の奴の一部分もしくは全部, minは最後のBを捨てるため
    memo[key] = sumP(level-1, lens[level-1]) + 1 + sumP(level-1, min(lens[level-1], index-lens[level-1]-2))
  return memo[key]

print(sumP(n, k))

Submission status: Accepted

Solution code:
n, k = list(map(int, input().split(' ')))
#l = {}
#l[0] = 'P'
#def f(index):
#  return l[index] if index in l else 'B' + f(index-1) + 'P' + f(index-1) + 'B'
# print(f(50)) dead
    #P
   #BPPPB
  #BBPPPBPBPPPBB
 #BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
#BBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBB
# length(x) = 2 * length(x-1) + 3
lens = {}
lens[0] = 0
lens[1] = 1
for i in range(2,52):
  lens[i] = lens[i-1] * 2 + 3
memo = {}
def sumP(level, index):
  key = (level, index)
  if key in memo:
    return memo[key]
  if level <= 0 or index <= 0:
    memo[key] = 0
  elif level == 1 and index == 1:
    memo[key] = 1
  elif index == lens[level] // 2 + 1:  # ど真ん中のPを入れて一つ下全部(index-1は左端のB)
    memo[key] = 1 + sumP(level-1, index-1)
  elif index < lens[level] // 2 + 1:  # レベル一つ下の奴の一部分のみ
    memo[key] = sumP(level-1, index-1)
  else: # レベル一つ下の奴の丸々1つ + P + レベル一つ下の奴の一部分もしくは全部
    memo[key] = sumP(level-1, lens[level-1]) + 1 + sumP(level-1, index-lens[level-1]-2)
  return memo[key]
print(sumP(n+1, k))  # level 1ずれてる！

#BBPPPBPBPPPBB = 13

Submission status: Accepted

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


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

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

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

    ans = 0
    now_level = N + 1
    for i in range(N+1):
        now_level -= 1
        pivot = (get_num_of_lay(now_level)+1)/2
        if X > pivot:#get a half party
            ans += get_num_of_paty(now_level-1)+1
            X -= pivot
        elif X == pivot:
            ans += get_num_of_paty(now_level-1)+1
            break
        else:
            X -= 1

    print(ans)


# Generated by 1.1.6 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:
n, x = map(int, input().split())

burgersize = [1]
beef_level = [2**i - 1 for i in range(1, n+2)]

a = 1
for i in range(n):
    a = 2*a + 3
    burgersize.append(a)


def eat(level, x):
    size = burgersize[level]
    half = (size + 1) // 2
    beef = beef_level[level]

    if size - 1 <= x:
        return beef

    elif x <= level:
        return 0

    elif level < x < half:
        return eat(level-1, x-1)

    elif x == half:
        return beef//2 + 1

    elif half < x < size - 1:
        return beef//2 + 1 + eat(level-1, x-half)

ans = eat(n, x)
print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
def doit(l, x):
    layers = 2 ** (l + 1) - 3
    if x >= layers * 2 + 3:
        return 2 ** (l + 1) - 1
    elif x >= layers + 2:
        return doit(l - 1, x - layers - 2) + 2 ** l
    elif x >= 1:
        return doit(l - 1, x - 1)
    else:
        return 0
print(doit(n, x))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
def layers(l):
    return 2 ** (l + 2) - 3
def patties(l):
    return 2 ** (l + 1) - 1
def doit(l, x):
    if x >= layers(l):
        return patties(l)
    y = layers(l - 1)
    ret = 0
    if x >= 1:
        ret += doit(l - 1, x - 1)
    if x >= y + 2:
        ret += 1
        ret += doit(l - 1, x - y - 2)
    return ret
print(doit(n, x))

Submission status: Accepted

Solution code:
N, X = [int(x) for x in input().split()]
h = [1]
b = [1]
for i in range(N):
    h.append(3 + h[i] * 2)
    b.append(1 + b[i] * 2)
def rec(n: int, x: int):
    if (n == 0):
        return 0 if x <= 0 else 1
    mid = 1 + h[n-1] + 1
    if (x < mid):
        return rec(n-1, x-1)
    if (x == mid):
        return b[n-1] + 1
    if (mid < x):
        return b[n-1] + 1 + rec(n-1, x-mid)
print(rec(N, X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
p=[0]*51
b=[0]*51
p[0]=1
for i in range(50):
    p[i+1]=2*p[i]+1
    b[i+1]=2*b[i]+2
def dfs(n,x):
    if x<=n:
        return 0
    if n==0:
        return 1
    z=p[n]+b[n]
    if z//2==x:
        return p[n-1]
    elif z//2+1==x:
        return p[n-1]+1
    elif z//2+1<x:
        return p[n-1]+1+dfs(n-1,x-z//2-1)
    else:
        return dfs(n-1,x-1)
print(dfs(n,x))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,x = inpl()
h = [1] * (n+1)
b = [0] * (n+1)
p = [1] * (n+1)
for i in range(1,n+1):
    h[i] = 3 + h[i-1] * 2
    b[i] = 2 + b[i-1] * 2
    p[i] = h[i] - b[i]
# print(h,p)
def sol(n,x):
    if n == 0 :
        return 1
    elif x == 1:
        return 0
    elif x <= 1 + h[n-1]:
        return sol(n-1, x-1)
    elif x == 2 + h[n-1]:
        return p[n-1] + 1
    elif x < h[n]:
        return p[n-1] + 1 + sol(n-1, x-(h[n-1]+2))
    else:
        return p[n-1] * 2 + 1
print(sol(n,x))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,x = inpl()
h = [1] * (n+1)
b = [0] * (n+1)
p = [1] * (n+1)
for i in range(1,n+1):
    h[i] = 3 + h[i-1] * 2
    b[i] = 2 + b[i-1] * 2
    p[i] = h[i] - b[i]
# print(h,p)
def sol(n,x):
    if n == 0 :
        return 0 if x <= 0 else 1
    elif x == 1:
        return 0
    elif x <= 1 + h[n-1]:
        return sol(n-1, x-1)
    elif x == 2 + h[n-1]:
        return p[n-1] + 1
    elif x < h[n]:
        return p[n-1] + 1 + sol(n-1, x-(h[n-1]+2))
    else:
        return p[n-1] * 2 + 1
print(sol(n,x))

Submission status: Accepted

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

x -= 1

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

length = length[::-1]
n_p = n_p[::-1]

ans = 0
for i in range(len(length)):

    if i == len(length) - 1:
        if x >= 0:
            ans += 1
    else:
        # print(x, ans, length[i+1])
        if x == length[i+1] + 1:
            ans += n_p[i+1] + 1
            break
        elif x == length[i+1]:
            ans += n_p[i+1]
            break
        elif x < length[i+1]:
            x -= 1
        else:
            x -= (length[i+1] + 2)
            ans += n_p[i+1] + 1

print(ans)

Submission status: Accepted

Solution code:
def stack(layer, length):
  if layer==1:
    return "BPPPB"[:length].count("P")
  else:
    if length==(lengths[layer-1]+1)/2:
      return ps[layer-2]+1
    elif length<(lengths[layer-1]+1)/2:
      return stack(layer-1, length-1)
    else:
      return ps[layer-2]+1+stack(layer-1, length-lengths[layer-2]-2)
    
inp = input().split()
layer = int(inp[0])
length = int(inp[1])
lengths = [5]
ps = [3]
for i in range(49):
  lengths.append(lengths[i]*2+3)
  ps.append(ps[i]*2+1)
print(stack(layer, length))

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache


@lru_cache(maxsize=None)
def alg_memoization_recursion(lv, n, m):
    if lv == 0:
        if m <= 0:
            return 0
        else:
            return 1
    else:
        if (n + 1) // 2 == m:
            return alg_memoization_recursion(lv - 1, n // 2 - 1, m - 1) + 1
        elif (n + 1) // 2 > m:
            return alg_memoization_recursion(lv - 1, n // 2 - 1, m - 1)
        elif n == m:
            return alg_memoization_recursion(lv - 1, n // 2 - 1, n // 2 - 1) + alg_memoization_recursion(lv - 1, n // 2 - 1, m - (n // 2) - 1) + 1
        else:
            return alg_memoization_recursion(lv - 1, n // 2 - 1, n // 2 - 1) + alg_memoization_recursion(lv - 1, n // 2 - 1, m - (n // 2) - 1) + 1


def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    n, x = list(map(int, input().rstrip('\n').split()))
    t = 1
    for i in range(1, n + 1):
        t = 1 + t + 1 + t + 1
    print(alg_memoization_recursion(n, t, x))


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

def rec(level, X) :
    if level == 0 :
        return 1
        
    if X == 1 :
        return 0
        
    elif X <= 2 ** (level + 1) - 2 :
        return rec(level - 1, X - 1)
        
    elif X == 2 ** (level + 1) - 1 :
        return 2 ** level
        
    elif X <= 2 ** (level + 2) - 4 :
        return 2 ** level + rec(level - 1, X - (2 ** (level + 1) - 1))
        
    else :
        return 1 + (2 ** level - 1) * 2
        
print(rec(N, X))

Submission status: Accepted

Solution code:
# D - Christmas

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

height = [1] # レベルiバーガーの高さ
for _ in range(N):
    height.append(height[-1]*2 + 3)
    
patty = [1] # レベルiバーガーに含まれるパティの総数
for _ in range(N):
    patty.append(patty[-1]*2 + 1)

def dp(n,x): # レベルnバーガーの下からx個の層に含まれるパティの数
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x <= 1 + height[n-1]:
        return dp(n-1, x-1)
    elif x == 2 + height[n-1]:
        return patty[n-1] + 1
    elif 2 + height[n-1] < x <= height[n] - 1:
        return patty[n-1] + 1 + dp(n-1, x - (height[n-1] + 2))
    else:
        return patty[n]
    
print(dp(N,X))

Submission status: Accepted

Solution code:
L,X=map(int,input().split())
b=[1];p=[1]
for i in range(L):
	b.append(b[-1]*2 + 3)
	p.append(p[-1]*2 + 1)
def f(L, X):
	if L==0 or X<0:
		return 0 + (X>0)
	elif X <= 1 + b[L-1]:
		return f(L-1, X-1)
	else:
		return p[L-1] + 1 + f(L-1, X-b[L-1]-2)
print(f(L, X))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
size = [1]
pati = [1]
for i in range(n):
    size.append(size[i]*2 + 3)
    pati.append(pati[i]*2 + 1)
ans = 0
for i in range(n):
    if x == 1:
        x -= 1
        break
    elif x == size[n-i]:
        ans += pati[n-i]
        break
    elif x == size[n-i-1]+2:
        ans += pati[n-i-1]+1
        break
    elif x > size[n-i-1] + 2:
        ans += pati[n-i-1]+1
        x -= size[n-i-1] + 2
    else:
        x -= 1
if x == 1:
    ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
n, x = map(int, input().split())
b = [2**(i+2) - 3 for i in range(51)]
p = [2**(i+1) - 1 for i in range(51)]
def pate(m, k):
    if m == 0:
        return k
    else:
        if k == 0:
            return 0
        elif k <= b[m-1] + 1:
            return pate(m-1, k-1)
        elif k == b[m-1] + 2:
            return p[m-1] + 1
        elif k <= b[m] -1:
            return p[m-1] + 1 + pate(m-1, k-b[m-1]-2)
        else:
            return p[m]
print(pate(n, x))

Submission status: Accepted

Solution code:
n,x=map(int,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+(x>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:
def func(l, u, x, t):
    if len(l) == 0:
        return t+1
    else:
        p = l[-1]
        q = u[-1]
        if x == 1:
            return t
        elif 1 < x <= 1 + p:
            return func(l[:-1], u[:-1], x - 1, t)
        elif x == 2 + p:
            t += u[-1] + 1
            return t
        elif 2 + p < x <= 2 + 2 * p:
            t += u[-1] + 1
            return func(l[:-1], u[:-1], x - (2 + p), t)
        elif x == 3 + 2 * p:
            t += 2 * u[-1] + 1
            return t

n,x  = [int(_) for _ in input().split()]
l = []
for i in range(0, n):
    if i == 0:
        l.append(1)
    else:
        l.append(l[-1]*2+3)
u = []
for j in range(0, n):
    if j == 0:
        u.append(1)
    else:
        u.append(u[-1]*2+1)

print(func(l, u, x, 0))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
 
#レベルnバーガーの構造は、1,2^(n+1)-3,1,2^(n+1)-3,1
 
ans = 0
x2 = x
k=n
while True:
  thk = [1,2**(k+1)-3,1,2**(k+1)-3,1]
  pc = [0,2**k-1,1,2**k-1,0]
  for i in range(5):
    x2-=thk[i]
    if x2<0:
      x2+=thk[i]
      k-=1
      break
    elif x2==0:
      ans+=pc[i]
      print(ans)
      exit()
    else:
      ans+=pc[i]

Submission status: Accepted

Solution code:
n, k = [ int(v) for v in input().split() ]
burgur = [ (0,0,0,1) ]
for _ in range(51):
    x, y, z, w = burgur[-1]
    y = w + 1
    z = 2 * w + 2
    w = 2 * w + 3
    burgur.append((x,y,z,w))

def eat(level,position):
    left, middle, right, _length = burgur[level]
    if level == 0:
        return 1
    else:
        if position == left:
            return 0
        elif position == middle:
            return 2**level
        elif position == right:
            return 2**(level+1) - 1
        elif left< position < middle:
            return eat(level-1, position-1)
        elif middle< position < right:
            return 2**level + eat(level-1, position-middle-1)

print(eat(n,k-1))

Submission status: Accepted

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

burger = [1]*(n+1)
patty = [1]*(n+1)

stopped = 0
for i in range(1,n+1):
	burger[i] = 2*burger[i-1]+3
	patty[i] = 2*patty[i-1]+1
	
def solve(n, x):
	if x == 0:
		return 0
	elif x == burger[n]:
		return patty[n]
	elif x == burger[n-1]+1:
		return patty[n-1]
	elif x == burger[n-1]+2:
		return patty[n-1]+1
	elif x < burger[n-1]+2:
		return solve(n-1, x-1)
	elif x > burger[n-1]+2:
		return solve(n-1, x-burger[n-1]-2)+patty[n-1]+1

print(solve(n, x))

Submission status: Accepted

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

burger = [1]*(n+1)
patty = [1]*(n+1)

stopped = 0
for i in range(1,n):
	burger[i] = 2*burger[i-1]+3
	patty[i] = 2*patty[i-1]+1
	
def solve(n, x):
	if n == 0:
		if x == 0:
			return 0
		else:
			return 1
	elif n == 1:
		if x == 0:
			return 0
		elif x == 1:
			return 0
		elif x == 2:
			return 1
		elif x == 3:
			return 2
		elif x == 4:
			return 3
		else:
			return 3
	elif x == 0:
		return 0
	elif x == burger[n]:
		return patty[n]
	elif x == burger[n-1]+1:
		return patty[n-1]
	elif x == burger[n-1]+2:
		return patty[n-1]+1
	elif x < burger[n-1]+2:
		return solve(n-1, x-1)
	elif x > burger[n-1]+2:
		return solve(n-1, x-burger[n-1]-2)+patty[n-1]+1

print(solve(n, x))

Submission status: Accepted

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

count_p = [1] * (N+1) # パティの数
for i in range(1, N+1):
    count_p[i] += count_p[i-1] * 2

length = [1] * (N+1) # バーガーの長さ
for i in range(1, N+1) :
    length[i] += (length[i-1] + 1) * 2

def F(n, x): # レベルnバーガーの下x層のあるパティの数
    if n == 0:
        return min(1, x)
    if x == length[n] // 2 + 1:
        return count_p[n-1] + 1
    elif x > length[n] // 2 + 1:
        return count_p[n-1] + 1 + F(n-1, x-(length[n]//2+1))
    else:
        return F(n-1, max(0, x-1))
print(F(N, X))

Submission status: Accepted

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

count_p = [1] * (N+1) # パティの数
for i in range(1, N+1):
    count_p[i] += count_p[i-1] * 2

length = [1] * (N+1) # バーガーの長さ
for i in range(1, N+1) :
    length[i] += (length[i-1] + 1) * 2

def F(n, x): # レベルnバーガーの下x層のあるパティの数
    if n == 0:
        return 0 if x <= 0 else 1
    if x == length[n] // 2 + 1:
        return count_p[n-1] + 1
    elif x > length[n] // 2 + 1:
        return count_p[n-1] + 1 + F(n-1, x-(length[n]//2+1))
    else:
        return F(n-1, max(0, x-1))
print(F(N, X))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
b=[0]*(n+1)
p=[0]*(n+1)
s=[0]*(n+1)
p[0]=1
s[0]=1
for i in range(1,n+1):
    b[i]=2+b[i-1]*2
    p[i]=1+p[i-1]*2
    s[i]=b[i]+p[i]
count=0
for i in range(n):
    i=n-1-i
    if x==0:
        break
    x-=1
    if x>=s[i]:
        x-=s[i]
        count+=p[i]
        if x==0:
            break
        x-=1
        count+=1
        if x>=s[i]:
            x-=s[i]
            count+=p[i]
            break
print(count)

Submission status: Accepted

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

# Level nバーガーの層数とパティの総数
burgers = [0] * (N + 1)
patty = [0] * (N + 1)
burgers[0] = 1
patty[0] = 1
for i in range(1, N + 1):
    burgers[i] = 3 + burgers[i - 1] * 2
    patty[i] = 1 + patty[i - 1] * 2


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


print(f(N, X))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
def meet(n,x):
    total = 2**(n+2)-3
    if n == 1:
        bur = 'BPPPB'
        return bur[:x].count('P')
    else:
        if x < total//2+1:
            return meet(n-1,x-1)
        if x == total//2+1:
            return 2**n
        else:
            if x != total:
                return 2**n+meet(n-1,x-total//2-1)
            else:
                return 2**n+meet(n-1,2**(n+1)-3)

print(meet(n,x))

Submission status: Accepted

Solution code:
N, X = map(int,input().split())
thk = [1]
p = [1]

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy,copy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
    n,x = MAP()
    L = [1]*n
    P = [1]*n

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

    def func(N, X):
        if N==0:
            return 0 if X <= 0 else 1

        elif X<= L[N-1] + 1:
            return func(N-1, X-1)

        else:
            return P[N-1] + 1 + func(N-1, X-L[N-1] -2)

    print(func(n,x))

if  __name__=='__main__':
    main()