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:
# -*- coding: utf-8 -*-


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

    # KeyInsight
    # 再帰的な構造を見抜いて，条件に応じて場合分け
    # See:
    # http://drken1215.hatenablog.com/entry/2019/05/13/114600
    # ◯気がつけた点
    # ・バーガーとパティの量が，レベルが高くなるにつれて規則的に増える
    # ・再帰を使えば良さそう
    # △気がつけなかった点
    # ・規則性のある状態をどう再帰関数として，定式化するか
    def f(n, x):
        # 終了条件
        if n == 0:
            return 1

        # Nレベルバーガーから，N - 1レベルバーガーになるときの枚数の変化
        total_length = 2 ** (n + 1) - 3
        p_count = 2 ** n - 1

        # イメージ
        # B：バン，P：パティ
        # Nレベルバーガー：B(N - 1レベルバーガー)P(N - 1レベルバーガー)B
        if x == 1:
            # Bのみ
            return 0
        elif x <= total_length + 1:
            # B(N - 1レベルバーガー)
            # レベルを一つ減らす．N - 1レベルバーガーの中身を見るため，最下層のBは見なくてもよくなる
            return f(n - 1, x - 1)
        elif x <= total_length + 2:
            # B(N - 1レベルバーガー)P
            # N - 1レベルバーガーのパティ + 1枚
            return p_count + 1
        elif x <= 2 * (total_length + 1):
            # B(N - 1レベルバーガー)P(N - 1レベルバーガー)
            # N - 1レベルバーガーのパティ + 1枚と，上側にある（N - 1レベルバーガーのパティの数）
            return p_count + 1 + f(n - 1, x - total_length - 2)
        else:
            # B(N - 1レベルバーガー)P(N - 1レベルバーガー)B
            return 2 * p_count + 1

    print(f(n, x))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

print(burger(n,x))

Submission status: Accepted

Solution code:
from sys import stdin

N, X = [int(x) for x in stdin.readline().rstrip().split()]
burger = [(1, 1)]
level = 0

while level < N:
    burger.append((burger[-1][0] * 2 + 3, burger[-1][1] * 2 + 1))
    level += 1

ans = 0
while N > 0 and X > 0:
    if X < burger[N - 1][0] + 2:
        N -= 1
        X -= 1
    if X == burger[N - 1][0] + 2:
        ans += 1
        X -= 2
        N -= 1
    if burger[N - 1][0] + 2 < X:
        X -= burger[N - 1][0] + 2
        ans += burger[N - 1][1] + 1
        N -= 1
if N == 0 and X > 0:
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)

def solve(n, x):
  if n == 0:
    if x > 0:
      return 1
    else:
      return 0
  else:
    ans = 0
    burger_prev = 2**(n+1)-3
    pate_prev = 2**n-1
    if x > 1:
      if x < burger_prev+1:
        ans += solve(n-1 ,x-1)
      else:
        ans += pate_prev
        if x > burger_prev+1:
          ans += 1
          if x > burger_prev*2+2:
            ans += pate_prev
          else:
            ans += solve(n-1, x-2-burger_prev)
    return ans

N, X = map(int, input().split())
print(solve(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[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-a[n-1]-2)
print(f(n,x))

Submission status: Accepted

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

d=[1 for i in range(n+1)]
p=[1 for i in range(n+1)]

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

def bp(n,x):
  if x==d[n]:
    return p[n]
  if x==1:
    return 0
  if x==2+d[n-1]:
    return 1+p[n-1]
  if x<2+d[n-1]:
    return bp(n-1,x-1)
  if x<d[n]:
    return 1+p[n-1]+bp(n-1,x-d[n-1]-2)

print(bp(n,x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
def eat(n,x):
    if x==0:
        return 0
    if n==0 and x==1:
        return 1
    
    if n>=1:
        if x<=2**(n+1)-2:
            return eat(n-1,x-1)
        elif x==2**(n+1)-1:
            return eat(n-1,2**(n+1)-3)+1
        elif 2**(n+2)-3>x>=2**(n+1):
            return eat(n-1,2**(n+1)-3)+1+eat(n-1,x+1-2**(n+1))
        elif x==2**(n+2)-3:
            return 2*eat(n-1,2**(n+1)-3)+1
print(eat(n,x))

Submission status: Accepted

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

a_list = [0]*(n+1)
a_list[0] = 1
p_list = [0]*(n+1)
p_list[0] = 1
for i in range(1, n+1):
    a_list[i] = 2 * a_list[i-1] + 3
    p_list[i] = 2 * p_list[i-1] + 1


def Recursive_function(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1
    elif x <= a_list[n-1] + 1:
        return Recursive_function(n - 1, x - 1)
    elif x == a_list[n-1] + 2:
        return p_list[n-1] + 1
    elif x == 2 * a_list[n-1] + 3:
        return 2 * p_list[n-1] + 1
    else:
        return p_list[n-1] + 1 + Recursive_function(n-1, x - 2 - a_list[n-1])


print(Recursive_function(n, x))

Submission status: Accepted

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

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)

# レベル lv のバーガーの下から x 枚に含まれるパティの数
def f(lv, x):
    if lv == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + a[lv-1]:
        return f(lv-1, x-1)
    else:
        return p[lv-1] + 1 + f(lv-1, x -1 -a[lv-1] -1)

def main():
    print(f(N,X))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

ans = 0
def f(lv):
    global ans, X
    if X == total[lv]:
        ans += pate[lv]
    else:
        X -= 1
        if X > 0:
            if X < total[lv-1]:
                f(lv-1)
            else:
                ans += pate[lv-1]
                X -= total[lv-1]                
                if X > 0:
                    ans += 1
                    X -= 1
                if X > 0:
                    f(lv-1)
                if X > 0:
                    X -= 1 # unreachable?

def main():
    f(N)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,X=map(int,input().split())

X-=1
def saiki(i,x,count):
    if i==-1:
        print(int(count)+1)
        exit()
    all=2**(i+2)-3
    paty=2**(i+1)-1
    if x==all-1:
        print(count+paty)
        exit()
    elif x==0:
        print(count)
    elif x==(all-1)//2:
        print(int(count+(paty-1)//2+1))
        exit()
    elif x>(all-1)//2:
        count+=((paty-1)//2+1)
        x-=(all//2)
        saiki(i-1,x-1,count)
    elif x<(all-1)//2:
        saiki(i-1,x-1,count)
    

ans=0
saiki(N,X,ans)

Submission status: Accepted

Solution code:
#%%
N, X = map(int, input().split())
point = []
ans = 0

a = 1
p = 1
for i in range(N):
    a *= 2
    a += 3
    p *= 2
    p += 1

#print(a, p)

while a >= 1:
    if X == a :
        ans += p
        break
    elif (a+1)//2+1 <= X <= a-1:
        X -= 2+(a-3)//2
        ans += p//2 + 1
    elif  X == (a+1)//2:
        ans += p//2 + 1
        break
    elif 2 <= X <= (a+1)//2-1:
        X -= 1
    elif X == 1:
        break

    a -= 3
    a //= 2
    p -= 1
    p //= 2

    #print(a, p)

print(ans)

Submission status: Accepted

Solution code:
line = [int(x) for x in input().strip().split()]

N = line[0]
X = line[1]


patties = [1]
buns = [0]
layers = [1]
for i in range(1, 51):
	patties.append(patties[i - 1] * 2 + 1)
	buns.append(buns[i - 1] * 2 + 2)
	layers.append(patties[i] + buns[i])

def answer(l, r, level):
	if (l > r):
		return 0
	if (l == 1 and r == layers[level]):
		return patties[level]

	mid = layers[level] // 2 + 1
	ans = 0
	if (r > mid):
		ans += 1
		ans += answer(1, layers[level - 1], level - 1)
		ans += answer(1, r - mid, level - 1)
	elif (r == mid):
		ans += 1
		ans += answer(1, layers[level - 1], level - 1)
	else:
		ans += answer(1, r - 1, level - 1)
	return ans

print(answer(1, X, N))

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# L = [list(input().strip())  for _ in range(N)]
# S = input().strip()

m = {}
def f(n):
    if m.get(n) != None:
        return m[n]
    if n == 0:
        m[n] = (1, 1)
    else:
        b = f(n - 1)
        m[n] = (b[0] * 2 + 3, b[1] * 2 + 1)
    return m[n]

f(N)

def ff(n, t):
    if n == 0:
        return 0 if t <= 0 else 1
    elif t <= 1 + m[n - 1][0]:
        return ff(n - 1, t - 1)
    else:
        return m[n - 1][1] + 1 + ff(n - 1, t - 2 - m[n - 1][0])

print(ff(N, M))

Submission status: Accepted

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

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

ans = 0
for i in range(n, -1, -1):
    layer = l[i]
    if x >= layer:
        ans += p[i]
        break
    elif x <= 1:
        break

    half = l[i - 1] + 1
    if x > half:
        ans += 1
        ans += p[i - 1]
        x -= half
        x -= 1
    elif x <= half:
        x -= 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n, x = map(int, input().split())

l = np.zeros(51, dtype=np.int64)
p = np.zeros(51, dtype=np.int64)

for i in range(n + 1):
    if i == 0:
        l[i] = 1
        p[i] = 1
        continue
    l[i] = 3 + 2 * l[i - 1]
    p[i] = 1 + 2 * p[i - 1]

ans = 0
for i in range(n, -1, -1):
    layer = l[i]
    if x >= layer:
        ans += p[i]
        break
    elif x <= 1:
        break

    half = l[i - 1] + 1
    if x > half:
        ans += 1
        ans += p[i - 1]
        x -= half
        x -= 1
    elif x <= half:
        x -= 1

print(ans)

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
dp_a=[1]
dp_p=[1]
for i in range(1,n):
  dp_a.append(2*dp_a[i-1] + 3)
  dp_p.append(2*dp_p[i-1] + 1)  
  
def burger(n,x):
  if n==0:
    if x <= 0:      
      return 0
    else:
      return 1
    
  if x <= dp_a[n-1]+1:
    return burger(n-1, x-1)
  else:
    return dp_p[n-1] +1 +burger(n-1, x-dp_a[n-1]-2)  

print(burger(n,x))

Submission status: Accepted

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

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

    ALL = [0] * (N+1)
    PATE = [0] * (N+1)
    ALL[0] = 1
    PATE[0] = 1
    for i in range(1, N+1):
        ALL[i] = ALL[i-1] * 2 + 3
        PATE[i] = PATE[i-1] * 2 + 1
    
    def dfs(level, remain):
        if level == 0:
            return 1
        ans = 0
        # バン
        if remain > 0:
            remain -= 1
        # レベルL-1バーガー
        if remain > 0:
            if remain >= ALL[level - 1]:
                remain -= ALL[level - 1]
                ans += PATE[level - 1]
            else:
                ans += dfs(level - 1, remain)
                remain = 0
        # パティ
        if remain > 0:
            remain -= 1
            ans += 1
        # レベルL-1バーガー
        if remain > 0:
            if remain >= ALL[level - 1]:
                remain -= ALL[level - 1]
                ans += PATE[level - 1]
            else:
                ans += dfs(level - 1, remain)
                remain = 0
        # バン
        if remain > 0:
            remain -= 1
        return ans
    
    print(dfs(N, X))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

rayers = [0] * (N+1)
rayers[0] = 1
Ps = [0] * (N+1)
Ps[0] = 1
for i in range(1,N+1):
    rayers[i] = 3 + 2*rayers[i-1] # B{L-1}P{L-1}B
    Ps[i] = 1 + 2*Ps[i-1] # そのレベルのPの数は前のレベルの数*2＋1こ

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

    if X <= rayers[N-1]+1:
        # 食べる枚数が、Nレベルバーガーの中心より手前の時、その一レベル下のバーガーから底のBを一枚除いて食べるのと同じ
        return solve(N-1, X-1)
    elif X == rayers[N-1]+2:
        # Nレベルバーガーのちょうど真ん中まで食べるとき
        return Ps[N-1] + 1 
    elif X > rayers[N-1]+2:
        # 真ん中より先の方まで食べるとき
        return Ps[N-1] + 1 + solve(N-1, X - rayers[N-1] - 2)

print(solve(N,X))

Submission status: Accepted

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

a = [1] #i番目にはi番目に作られるハンバーガーの大きさが入っている : a[i+1] = 2 * a[i] + 3
p = [1] #i番目にはi番目に作られるハンバーガーのパティの枚数　: p[i+1] = 2 * p[i] + 1
for i in range(N):
    a.append(2*a[i]+3)
    p.append(2*p[i]+1)
def function(N,X):
    if N <= 0 :
        return 0 if X<= 0 else 1
    elif X <= a[N-1] + 1 :
        ret = function(N-1,X-1)
        return ret
    else:
        ret  = 1 + p[N-1]
        ret +=  function(N-1,X-a[N-1]-2)
        return ret
print(function(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[i]*2+3)
	p.append(p[i]*2+1)
def f(n,x):
	if n==0:
		if x<=0:
			return 0
		else:
			return 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())
h = [1]
p = [1]
for i in range(N):
    h.append(h[i]*2+3)
    p.append(p[i]*2+1)
def f(N,X):
    if X == 1:
        if N == 0:
            return 1
        return 0
    elif 1 < X and X <= 1 + h[N-1]:
        return f(N-1,X-1)
    elif X == 2 + h[N-1]:
        return p[N-1] + 1
    elif 2 + h[N-1] < X and X <= 2 + 2 * h[N-1]:
        return p[N-1] + 1 + f(N-1,X-2-h[N-1])
    elif X == 3 + 2 * h[N-1]:
        return p[N]
print(f(N,X))

Submission status: Accepted

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

p = [1]
h = [1]

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


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

    if x <= 1 + h[n - 1]:
        return f(n - 1, x - 1)

    return p[n - 1] + 1 + f(n - 1, x - 2 - h[n - 1])


print(f(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[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(10 ** 9)

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

def patty(l,x):
  if l == 0:
    res = 1
  else:
    if x == 1:
      res = 0
    elif 2 <= x <= L[l-1]+1:
      res = patty(l-1,x-1)
    elif x == L[l-1]+2:
      res = patty(l-1,L[l-1])+1
    elif L[l-1]+3 <= x <= L[l-1]*2+2:
      res = patty(l-1,L[l-1])+1+patty(l-1,x-L[l-1]-2)
    else:
      res = patty(l-1,L[l-1])*2+1
  return res

print(patty(N,X))

Submission status: Accepted

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

def main(n, x):
    if n == 0:
        if x >= 0:
            return 1
        else:
            return 0
    if x == 0:
        return 0
    if x == 2 ** (n + 1) - 2:
        return 2 ** n
    if x < 2 ** (n + 1) - 2:
        return main(n - 1, x - 1)
    if x > 2 ** (n + 1) - 2:
        return 2 ** n + main(n - 1, x - (2 ** (n + 1) - 1))
print(main(n, x))

Submission status: Accepted

Solution code:
def count(n, x):
    b1 = 1<<n
    b2 = b1<<1
    return 1 if n == 0 else \
           0 if x == 1 else \
           count(n-1, x-1) if x <b2-1 else \
           b1 if x == b2-1 else \
           count(n-1, x+1-b2)+b1 \

N, X = map(int, input().split())
print(count(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[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())

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

def rec(n, x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    if x * 2 > h[n]:
        return 2 ** n + rec(n - 1, x - 1 - h[n] // 2)
    return rec(n - 1, x - 1)

print(rec(n, x))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
n, x = map(int, input().split())
a, p = [1], [1]
for i in range(n):
    a.append(2*a[i]+3)
    p.append(2*p[i]+1)


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

print(f(n,x))

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 func(N, X):
        if N == 0:
            return 0 if X <= 0 else 1
        elif X <= 1 + a[N-1]:
            return func(N-1, X-1)
        else:
            return p[N-1] + 1 + func(N-1, X-2-a[N-1])

    print(func(N,X))

main()

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

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:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)

"""考え方
L0 : P
L1 : BPPPB
L2 : BBPPPBPBPPPBB
L3 : BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
L4 : ...

・レベルが1上がると、Pの数は2倍+1になる
・レベルが1上がると、総数は2倍+3になる


レベルiバーガーの厚さ（層の総数）をa_iとする
レベルiバーガーに含まれるパティの総数をp_iとする
「レベルNバーガーの下からX層に含まれるパティの枚数」をf(N,X)とする。

・N = 0のとき
f(0,X) = 1

・N >= 1のとき
f(N-1, Y)がわかると仮定すると、

(1) X = 1のとき、f(N,X) = 0 (一番下のバンだけ)

(2) 1 < X <= 1 + a_{i-1} のとき、f(N,X) = f(N-1, X-1)

i=2のとき、L2のときで
BBPPPB PBPPPBB
BPPPBB|ここまでのとき

(3) X = 2 + a_{i-1}のとき、f(N,X) = p_{i-1}+1
???


https://www.youtube.com/watch?v=1ONpCPN-IR8
"""
def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる


    def _dfs(depth, x):
        """ レベルdepthバーガーの、下からX層に含まれるパティの枚数を返す """
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[depth-1]:
            # 一番下のパン + その上のレベル N-1 バーガー + その上のパティ
            return _dfs(depth-1, x-1)
        else:
            # (前略) + その上のパティ + その上のレベル N-1 バーガーの下から x-2-As[depth-1]層
            return Ps[depth-1] + 1 + _dfs(depth-1, x-2-As[depth-1])

    ans = _dfs(N, X)

    print(ans)


def solve2():
    N, X = list(map(int, sys.stdin.readline().split()))

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


def solve3():
    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    # dpでもいけるはず？


if __name__ == "__main__":
    solve2()

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
L = [1] * n
P_num = [1] * n

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

def pati_num(n, x):
  if n == 0:
    if x >= 1:
      return 1
    else:
      return 0
  elif x <= 1 + L[n-1]:
    return pati_num(n-1, x-1)
  else:
    return P_num[n-1] + 1 + pati_num(n-1, x-2-L[n-1])
print(pati_num(n, x))

Submission status: Accepted

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

def layers(L):
  if L == 0:
    return 1
  else:
    return layers(L-1)*2+3
  
def patties(L,X):
  if L == 0:
    return 1
  elif X == 1:
    return 0
  elif X <= layers(L)//2:
    return patties(L-1,X-1)
  elif X == layers(L)//2+1:
    return layers(L-1)//2+2
  elif layers(L)//2+2 <= X <= layers(L)-1:
    return layers(L-1)//2+2+patties(L-1,X-layers(L)//2-1) 
  else:
    return layers(L)//2+1
    
print(patties(n,x))

Submission status: Accepted

Solution code:
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 1+p[n-1]+f(n-1,x-2-b[n-1])

N,X=map(int,input().split())
b,p = [1 for _ in range(N+1)],[1 for _ in range(N+1)]

for i in range(1,N+1):
    b[i] = b[i-1]*2+3
    p[i] = p[i-1]*2+1
print(f(N,X))

Submission status: Accepted

Solution code:
def f(n):
    return 2**(n+2)-3
def g(n):
    return 2**(n+1)-1
def p(x,n):
    if x==1:
        return 0
    if n==1:
        if 2<=x<=4:
            return x-1
        elif x>4:
            return 3
    if x==f(n-1)+2:
        return g(n-1)+1
    if x>=2*f(n-1)+2:
        return 2*g(n-1)+1
    if x<f(n-1)+2:
        return p(x-1,n-1)
    if x<2*f(n-1)+2:
        return g(n-1)+1+p(x-f(n-1)-2,n-1)
N,X = map(int,input().split())
print(p(X,N))

Submission status: Accepted

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

total_counts = [1]
p_counts = [1]
for i in range(1, n + 1):
    total_counts.append(total_counts[-1] * 2 + 3)
    p_counts.append(p_counts[-1] * 2 + 1)


def count(x, n):
    if n == 0:
        return 1 if x > 0 else 0
    if x >= (total_counts[n] + 1) // 2:
        return p_counts[n - 1] + 1 + count(x - total_counts[n - 1] - 2, n - 1)
    else:
        return count(x - 1, n - 1)


print(count(x, n))

Submission status: Accepted

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


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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, X = [int(i) for i in input().split()]
p = [1]
l = 1
for i in range(N):
    p.append(p[-1] * 2 + 1)
    l = 2 * l + 3
ban_l = 1
ban_r = l
pate = l//2+1
cnt = 0
for i in range(N+1):
    if X == pate:
        if pate == ban_l:
            cnt += 1
            break
        else:
            cnt += p[N-(i+1)] + 1
            break
    elif X == ban_l:
        break
    elif X < pate:
        ban_l = ban_l + 1
        ban_r = pate - 1
        pate = (pate+ban_l)//2
    elif X < ban_r:
        cnt += p[N-(i+1)] + 1
        ban_l = pate + 1
        pate = (pate+ban_r)//2
        ban_r = ban_r - 1
    else:
        cnt += p[N-i]
        break
print(cnt)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())  # レベルNバーガー, 下からX層食べる

# そのレベルのバーガーにどれだけパティが含まれているかP
# そのレベルのバーガーが何層で成り立っているかA
P = [1]
A = [1]

for i in range(1, N+1):
    P.append(2**(i+1)-1)
    A.append(2**(i+2)-3)

# print(P)
# print(A)


def f(N, X):  # レベルNバーガーの下からX層に含まれる肉の数
    if N == 0:
        return 0 if X <= 0 else 1  # レベル0バーガーは肉1枚という仕様, レベル0バーがーの下から1枚（X > 0）を食べたら肉を1枚食べたことになる, 両方0のときにのみ肉は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:
#14:22
n,k = map(int,input().split())
whole = [1]
patty = [1]
for _ in range(n):
  whole.append(whole[-1] * 2 + 3)
  patty.append(patty[-1] * 2 + 1)
ans = 0
rest = k
for i in range(n,-1,-1):
  if i == 0:
    ans += [0,1,2,3,3][rest]
    rest = 0
  elif rest <= whole[i] - (i-1):
    rest -= 1
  elif rest <= whole[i]:
    rest = 0
    ans += patty[i]
  elif rest == whole[i] + 1:
    rest -= whole[i] + 1
    ans += patty[i] + 1
  else:
    rest -= whole[i] + 2
    ans += patty[i] + 1
  if rest == 0:
    print(ans)
    break

Submission status: Accepted

Solution code:
n, x = [int(x) for x in input().split()]
def patties(n):
    return 1 if n == 0 else 2 * patties(n - 1) + 1
def layers(n):
    return 1 if n == 0 else 2 * layers(n - 1) + 3
def eat(n, x):
    if n == 0:
        return x
    else:
        if x <= layers(n - 1) + 1:
            return eat(n - 1, max(0, x - 1))
        elif x == layers(n):
            return patties(n)
        else:
            return patties(n - 1) + 1 + eat(n - 1, x - (layers(n - 1) + 1) - 1)

print(eat(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[i]*2 + 3)
    p.append(p[i]*2 + 1)

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

print(calc(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[i] * 2 + 3)
  p.append(p[i] * 2 + 1)

def f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
  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())
p = 1
t = 1
pdic = {}
tdic = {}
for i in range(N):
  pdic[i] = p
  tdic[i] = t
  p = 2*p+1
  t = 2*t+3
pdic[N] = p
tdic[N] = t
ans = 0
nokori = X
state = N
count = N
while True:
  while tdic[count]+state-count>nokori:
    count -= 1
    if count<0:
      break
  if count<0:
    break
  nokori -= (tdic[count]+state-count)
  state = count
  ans += pdic[count]
  if nokori==0:
    break
  nokori -= 1
  ans += 1
  if nokori==0:
    break
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

    return helper(N, X, a, p)

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

if __name__ == '__main__':
    print(main())

Submission status: Accepted

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

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

def solve(N, cur):
    if N == 0:
        return 1 if cur > 0 else 0
        
    return solve(N-1, cur-1) if cur <= (layers[N] // 2) else solve(N-1, (cur-layers[N-1])-2) + patties[N-1] + 1

print(solve(n,x))

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 1
    if x == 1:
        return 0
    if 1 < x <= a[n - 1] + 1:
        return f(n - 1, x - 1)
    if x == a[n - 1] + 2:
        return p[n - 1] + 1
    if a[n - 1] + 2 < x <= 2 * a[n - 1] + 2:
        return p[n - 1] + 1 + f(n - 1, x - 2 - a[n - 1])
    if x == 2 * a[n - 1] + 3:
        return 2 * p[n - 1] + 1


print(f(N, X))

Submission status: Accepted

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

pos = X
eat = 0
for i in range(N-1, -1, -1):
    nlayer = 2 ** (i+2) - 3
    npatie = 2 ** (i+1) - 1
    if pos == 1:
        break
    elif pos <= 1 + nlayer:
        pos -= 1
        if i == 0:
            eat += 1
        continue
    elif pos == 2 + nlayer:
        eat += npatie + 1
        break
    elif pos <= nlayer * 2 + 2:
        eat += npatie + 1
        if i == 0:
            eat += 1
        pos -= nlayer + 2
    else:
        eat += npatie * 2 + 1
        break

print(eat)