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:
def func1(N):
    li = [1] * (N)
    for i in range(N-1):
        li[i+1] = li[i] *2+1
    return(li[N-1])
def func2(N):
    lia = [1] * (N)
    for i in range(N-1):
        lia[i+1] = lia[i] * 2 + 3
    return(lia[N-1])
N,X = [int(i) for i in input().split()]
def f(N,X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X<=1+func2(N):
        return f(N-1,X-1)
    else:
        return func1(N) + 1 + f(N-1,X-2-func2(N))
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(2*a[i] + 3)
    p.append(2*p[i] + 1)
    
def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    # 3つの場合分け
    mid = (a[n]+1)/2
    if x == mid:
        return 1 + p[n-1]
    elif x < mid:
        return f(n-1, x-1)
    elif x > mid:
        return f(n-1, x-mid) + 1 + p[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:
N,X = list(map(int,input().split()))

#[total,パティ数]
burger = [[1]*2 for i in range(51)]

ans = 0
for i in range(1,51):
    burger[i][0] = burger[i-1][0]*2+3
    burger[i][1] = burger[i-1][1]*2+1

    if X <= burger[i][0]:
        if i < N:
            X -= N-i
        while 0<X:
            X -= 1 #一番下のBを食う
            if X==0:
                break
            
            #中間まで食べられるかどうか
            if burger[i-1][0]<=X:
                X -= burger[i-1][0]
                ans += burger[i-1][1]

                if 0<X: #中間のPを食う
                    X -= 1
                    ans += 1
                else:
                    break
            
            #中間まで食べた後はL-1バーガー+B...Bが残る
            #中間まで食べられない場合はL-1バーガーのみ残ると考えて良い
            i -= 1
            if i == 0:
                if 0<X:
                    ans += 1
                #残りはパンだけor最初からなかったのと同じ
                break
        print(ans)
        break

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
A=[2**(i+2)-3 for i in range(0,N+1)]
pati=[2**(i+1)-1 for i in range(0,N+1)]
def function(num,level):
    if level==0:
        if num==1:
            return 1
        else:
            return 0
    elif num==1:
        return 0
    else:
        subslice=A[level-1]
        if subslice+1>=num:
            return function(num-1,level-1)
        elif num==subslice+2:
            return pati[level-1]+1
        elif A[level]-1>=num:
            return pati[level-1]+1+function(num-subslice-2,level-1)
        else:
            return pati[level]
print(function(X,N))

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
import math
import time
#import numpy as np
import collections
from collections import deque
import queue
import copy

# 最大公約数
def gcd(m,n):
  x = max(m,n)
  y = min(m,n)
  if x%y == 0:
    return y
  else:
    while x%y != 0:
      z = x%y
      x = y
      y = z
    else:
      return z

# 幅優先探索(BFS)でスタート座標(x, y)からの最大距離返す
def bfs(SS, x, y, H, W):#入力(座標系(迷路), x, y, xの端, yの端)
  x_next = [0, 0, -1, 1]
  y_next = [1, -1, 0, 0]
  tempx = x
  tempy = y
  mlength = 0
  q = deque()
  xytuple = (x, y, 0)
  q.append(xytuple)


  while q:
    xytuple = q.popleft()
    SS[xytuple[0]][xytuple[1]] = "x" #探索した場所は探索できないようにする
    for i in range(4): #このforで上下左右を調べてる
      tempx = xytuple[0] + x_next[i]
      tempy = xytuple[1] + y_next[i]
      #print(tempx, tempy, xytuple[2])
      #print(S)
      if(0 <= tempx and tempx < H and 0 <= tempy and tempy < W and SS[tempx][tempy] == "."):
        temptuple = (tempx, tempy, xytuple[2]+1)
        SS[temptuple[0]][temptuple[1]] = "x" #探索した場所は探索できないようにする
        mlength = max(mlength, xytuple[2] +1)
        q.append(temptuple)
      #print(q)
  return mlength

#素因数分解
def prime_factorize(n):
  a = []
  while n % 2 == 0:
    a.append(2)
    n //= 2
  f = 3
  while f * f <= n:
    if n % f == 0:
      a.append(f)
      n //= f
    else:
      f += 2
  if n != 1:
    a.append(n)
  return a

#重複を検出
def has_duplicates(seq):
  return len(seq) != len(set(seq))


#Christmas D問題
def Christmas(X, DP, DP2, N):
  ans = 0
  b = 0
  for i in reversed(range(0, N+1)):
    if(X-DP[i]>=0):
      b = DP[i]
      X -= b
      ans += DP2[i]
      if(X>=1):
        ans += 1
      N = i+1
      break
    X -= 1
    if(X == 0):
      break
  if not(X == 0):
    ans += Christmas(X, DP, DP2, N)

  return ans

#X = str(input()).split()
#a = [int(x) for x in input().split()]


NX = str(input()).split()
N = int(NX[0])
X = int(NX[1])
DP = [0]*51
DP2 = [0]*51
DP[0] = 1
DP2[0] = 1
ans = 0

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

ans = Christmas(X, DP, DP2, N)

print(ans)

Submission status: Accepted

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

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

print(calc(N, X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import *
from collections import *
from fractions import gcd
from math import factorial
from itertools import *
from heapq import *
import copy

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

P=[0 for i in range(N+1)]
P[0]=1
PB=[0 for i in range(N+1)]
PB[0]=1
for i in range(1,N+1):
    P[i]=1+2*P[i-1]
    PB[i]=3+2*PB[i-1]

count=0
idx=N

while X>0:
    A=PB[idx]
    if X>=A:
        X-=A
        count+=P[idx]
        if X>=1:
            count+=1
            X-=1
    else:
        X-=1
        idx-=1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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
    med = (a[n]+1) // 2
    if x < med:
        return f(n-1, x-1)
    elif x == med:
        return p[n-1] + 1
    elif x > med:
        return p[n-1] + 1 + f(n-1, x-med)
print(f(N, X))

Submission status: Accepted

Solution code:
# tokenakatta ...
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)
    return bur(N, X, a, p)
def bur(N, X, a, p):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X == 1:
        return 0
    elif X <= 1 + a[N-1]:
        return bur(N-1, X-1, a, p)
    elif X == 2 + a[N-1]:
        return p[N-1] + 1
    elif X <= 2 + 2 * a[N-1]:
        return p[N-1] + 1 + bur(N-1, X-2-a[N-1], a, p)
    else:
        return 2 * p[N-1] + 1
print(main())

Submission status: Accepted

Solution code:
def main():
    N, X = map(int, input().split())
    p, t = 1, 1
    P = [p]
    T = [t]
    for i in range(1, N + 1):
        p = p * 2 + 1
        t = t * 2 + 3
        P.append(p)
        T.append(t)
    r = 0
    i = N
    while i >= 0 and X > 0:
        if X >= T[i]:
            r += P[i]
            X -= T[i]
            if X >= 1:
                r += 1
                X -= 1
        else:
            X -= 1
            i -= 1
    print(r)
main()

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:
def count(n,x):
    if x<=n:
        return 0
    elif x>=2**(n+2)-3-n:
        return 2**(n+1)-1
    elif 2**(n+2)-3 > 2*x:
        return count(n-1,x-1)
    else:
        return 2**n + count(n-1,x-2**(n+1)+1)

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

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
pattis = [1]
buns = [0]

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

# print(pattis)
# print(buns)

def dfs(n , x):
    ## 終了条件
    if n == 0:
        return 1


    ## 0次元バーガー前に終了する条件
    burger_high = pattis[n] + buns[n]
    if x == 1:
        return 0
    elif x == burger_high:
        return pattis[n - 1] * 2 + 1
    elif x == burger_high // 2 + 1:
        return pattis[n - 1] + 1

    ## 再帰的に探索を続ける
    if 1 < x <= burger_high // 2:
        return dfs(n - 1, x - 1)
    elif burger_high // 2 < x < burger_high:
        return dfs(n - 1, x - (pattis[n - 1] + buns[n - 1] + 2)) + pattis[n - 1] + 1


print(dfs(N, X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
patty = [1]
buns = [0]

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


burger_high = patty[N] + buns[N]



def dfs(now_runrun, now_burger_high, dimension):
    if dimension == 0:
        return 1
    ## るんるんが一番下にいれば一つもパティは食べれない
    elif now_runrun == 1:
        return 0

    ## るんるんが真ん中にいたら、n - 1次元バーガー + 1を食べる
    elif now_runrun == now_burger_high // 2 + 1:
        return patty[dimension - 1] + 1

    ## るんるんが一番上にいたら全てのパティを食べる
    elif now_runrun == now_burger_high:
        return patty[dimension]


    next_burger = now_burger_high // 2 - 1
    next_dimension = dimension - 1

    if now_runrun <= now_burger_high // 2:
        return dfs(now_runrun - 1, next_burger, next_dimension)
    else:
        return dfs(now_runrun - (patty[next_dimension] + buns[next_dimension] + 2),
                   next_burger, next_dimension) + patty[next_dimension] + 1


print(dfs(X, burger_high, N))

Submission status: Accepted

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

li = [1]
li2 = [1]

for i in range(n):
    li.append(3+2*li[-1])
    li2.append(1+2*li2[-1])

ans = 0

for i in range(n):
    x -= 1
    if x >= li[-2-i]:
        x -= li[-2-i]
        ans += li2[-2-i]
    else:
        continue
    if x > 0:
        x -= 1
        ans += 1
    else:
        break
    if x >= li[-2-i]:
        x -= li[-2-i]
        ans += li2[-2-i]
    else:
        continue

print(ans)

Submission status: Accepted

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

l = [1]
p = [1]

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

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

print(result(n, x))

Submission status: Accepted

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

#レベルNの層とパティの数を求める
a,p=[1],[1]
for i in range(n):
    a.append(2*a[i]+3)
    p.append(2*p[i]+1)

def cnt(n,x):
    #レベルNのバーガーのX層までに含まれるパティを数える
    if n==0:
        return 1 if x>=1 else 0

    elif x<=1+a[n-1]:
        return cnt(n-1,x-1)

    elif 2+a[n-1]<=x:
        return cnt(n-1,x-(a[n-1]+2))+p[n-1]+1

print(cnt(n,x))

Submission status: Accepted

Solution code:
import sys, re, os
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
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 S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X = MAP()

# a_0 = 1, p_0 = 1
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
        if X > 0:
            return 1
    elif X <= a[N-1] + 1:
        return f(N-1, X-1)
    elif X > a[N-1] + 1:
        return p[N-1] + 1 + f(N-1, X - (a[N-1] + 1 + 1))

print(f(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
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect_left
from heapq import heappush, heappop

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

N, X = MAP()

a, p = [1]*N, [1]*N
for i in range(N-1):
	a[i+1] = a[i]*2+3
	p[i+1] = 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:
def hum(L,X):
    if L == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= 1 + t[L-1]:
        return hum(L-1,X-1)
    elif X <= 2 + 2 * t[L-1]:
        return p[L-1] + hum(L-1,X-2-t[L-1]) + 1
    else:
        return 2 * p[L-1] + 1

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

Submission status: Accepted

Solution code:
N, X = [int(_) for _ in input().split()]

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


def f(n, x):
    if n <= 0 and x == 1: return 1
    if x == 1: return 0
    if x <= A[n - 1] + 1:
        return f(n - 1, x - 1)
    if A[n - 1] + 2 == x:
        return P[n - 1] + 1
    if 2 * A[n - 1] + 3 > x:
        return P[n - 1] + 1 + f(n - 1, x - A[n - 1] - 2)
    else:
        return 2 * P[n - 1] + 1


print(f(N, X))

Submission status: Accepted

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

b = [1]
for _ in range(n + 1):
    b.append(b[-1] * 2 + 3)
c = [1]
for _ in range(n + 1):
    c.append(c[-1] * 2 + 1)

def a(x, n):
    if x == 0:
        return 0
    if n == 0:
        return c[0]
    x-=1
    ans = 0
    if x >= b[n - 1]:
        ans += c[n - 1]
        x -= b[n - 1]
    else:
        return a(x, n - 1)
    if x == 0:
        return ans
    elif x == 1:
        return ans + 1
    else:
        ans += 1
        x -= 1
        ans += a(x, n - 1)
        return ans
    
print(a(x,n))

Submission status: Accepted

Solution code:
#editorial参照
#再帰

m,y = map(int, input().split( ))
a = [1]
p = [1]
#あらかじめ作っておく
for i in range(m):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)
#場合分け、境界値

#入力と変数を一致させたが問題なかった
def f(m,y):#n,xにしないだけでバグる
    if m==0:
        return 0 if y<=0 else 1
    elif y <= 1+a[m-1]:
        return f(m-1,y-1)
    else:
        return p[m-1] + 1 + f(m-1, y-2 -a[m-1])

print(f(m,y))

Submission status: Accepted

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

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

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

#レベルiにおけるそれぞれの枚数，総数
P=[1]*(N+1)
B=[0]*(N+1)
S=[1]*(N+1)

for i in range(N):
    P[i+1]=P[i]*2+1
    B[i+1]=B[i]*2+2
    S[i+1]=P[i+1]+B[i+1]
    
def rec(l,x,temp):
    if x==0:
        return temp
    if x==S[l]:
        return temp+P[l]
    if x>=2+S[l-1]:#中心を超える
        return rec(l-1,x-(S[l-1]+2),temp+P[l-1]+1)
    return rec(l-1,x-1,temp)

print(rec(N,X,0))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
len_l=[0]*(n+1)
len_l[0]=1
num_p=[0]*(n+1)
num_p[0]=1
for i in range(n):
    len_l[i+1]=3+2*len_l[i]
    num_p[i+1]=2*num_p[i]+1
def calc(a,b):
    if a==0:
        return 1
    if b<=0:
        return 0
    else:
        nagasa=len_l[a]
        if b==1:
            return 0
        elif b<=len_l[a-1]+1:
            return calc(a-1,b-1)
        elif b==len_l[a-1]+2:
            return num_p[a-1]+1
        elif b<=2*len_l[a-1]+2:
            return num_p[a-1]+1+calc(a-1, b-(len_l[a-1]+2))
        elif b==2*len_l[a-1]+3:
            return 2*num_p[a-1]+1
        else:
            print('okasi')
            return None
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):
    if N == 0:
        return 1
    
    if X == 1:
        return 0

    if X <= 1 + a[N-1]:
        return f(N-1, X-1)

    if X == 2 + a[N-1]:
        return p[N-1] + 1

    if X <= 2 + 2 * a[N-1]:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

    if X == 3 + 2 * a[N-1]:
        return 2 * p[N-1] + 1


print(f(N, X))

Submission status: Accepted

Solution code:
from bisect import bisect_left


def dfs(n, X):
    p = bisect_left(layer[n], X)
    if n == 0:
        return 1
    if p == 0:
        return 0
    elif p == 1:
        return dfs(n - 1, X - 1)
    elif p == 2:
        return patty[n - 1] + 1
    elif p == 3:
        return patty[n - 1] + 1 + dfs(n - 1, X - layer[n][2])
    else:
        return 2 * patty[n - 1] + 1


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

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


patty = [0] * (N + 1)
patty[0] = 1
for i in range(N):
    t = patty[i]
    patty[i + 1] = 1 + 2 * t


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

print(f(N, X))

Submission status: Accepted

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


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

layers_num = []
p = []
for n in range(N):
    if n == 0:
        layers_num.append(len(level0))
        p.append(level0.count('P'))
    else:
        layers_num.append(layers_num[n - 1] * 2 + 3)
        p.append(2 * p[n - 1] + 1)

print(f(N - 1, X - 1))

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<=a[n-1]+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())
burger = [1]
patty = [1]

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

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

print(f(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:
    if x < 1:
      return 0
    else:
      return 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])
  
print(f(N, X))

Submission status: Accepted

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

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


def F(n, x):
    if n == 0:
        return 1
    if x == 1:
        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 + 2 * a[n - 1]:
        return p[n - 1] + 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 p_d():
    n, x = map(int, input().split())
    b, p = [1], [1]
    for i in range(n):
        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))


if __name__ == '__main__':
    p_d()

Submission status: Accepted

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

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)
print(pb(n,x))

Submission status: Accepted

Solution code:
import sys

def make_burger(n):
    patty = [None] * (n + 1)
    bun = [None] * (n + 1)
    patty[0] = 1
    bun[0] = 0
    burger = [None] * (n + 1)
    burger[0] = 1
    for i in range(n):
        patty[i+1] = patty[i] * 2 + 1
        bun[i+1] = bun[i] * 2 + 2
        burger[i+1] = patty[i+1] + bun[i+1]
    return burger, patty

burger, patty = make_burger(50)

def patty_cnt(l, r, res):
    if l == 0:
        return res + 1
    half_burger = burger[l] // 2 + 1
    half_patty = patty[l] // 2 + 1
    if r == 1:
        return res
    elif r < half_burger:
        return patty_cnt(l-1, r-1, res)
    elif r == half_burger:
        return res + half_patty
    elif r < burger[l]:
        return patty_cnt(l-1, r-half_burger, res+half_patty)
    elif r == burger[l]:
        return res + patty[l]
    
n, x = map(int, sys.stdin.readline().split())

def main():
    return patty_cnt(n, x, 0)
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys

def make_burger(n):
    patty = [None] * (n + 1)
    bun = [None] * (n + 1)
    patty[0] = 1
    bun[0] = 0
    burger = [None] * (n + 1)
    burger[0] = 1
    for i in range(n):
        patty[i+1] = patty[i] * 2 + 1
        bun[i+1] = bun[i] * 2 + 2
        burger[i+1] = patty[i+1] + bun[i+1]
    
    return patty, bun, burger

n, x = map(int, sys.stdin.readline().split())

def main():
    r = x
    patty, bun, burger = make_burger(n)

    res = 0
    for l in range(n, 0, -1):
        half_burger = burger[l] // 2 + 1
        half_patty = patty[l] // 2 + 1
        if r == 1:
            r = 0
            break
        elif r < half_burger:
            r -= 1
        elif r == half_burger:
            res += half_patty
            r = 0
            break
        elif r < burger[l]:
            res += half_patty
            r -= half_burger
        elif r == burger[l]:
            res += patty[l]
            r = 0
            break
    if r:
        res += 1
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,X=map(int,input().split())
    
    memo=[(0,0)]*N
    memo[0]=(1,1)
    for i in range(N-1):
        memo[i+1]=(memo[i][0]*2+3,memo[i][1]*2+1)
    def saiki(n,x):
        if n==0:
            return 1 if x>0 else 0
        if memo[n-1][0]+2<x:
            return memo[n-1][1]+saiki(n-1,x-(memo[n-1][0]+2))+1
        elif memo[n-1][0]+2==x:
            return memo[n-1][1]+1
        else:
            return saiki(n-1,x-1)
    print(saiki(N,X))
        

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc115/tasks/abc115_d
# 真面目に再帰関数によって文字列を生成すると、長さが爆発してしまう
# 問題の再帰構造を観察すると、二分探索のような処理でPの数を確定できる


def ret_length(L):
    ret = 1
    for _ in range(L):
        ret = 2 * ret + 3
    return ret


def ret_nP(L):
    ret = 1
    for _ in range(L):
        ret = 2 * ret + 1
    return ret


N, X = list(map(int, input().split()))
X -= 1  # X枚目まで食べるという扱いにする (0based index)

lng = ret_length(N)
nP = ret_nP(N)

# print(lng, nP, X)

ans = 0
l = 0
r = lng - 1
# while r - l > 0:  # lrが隣り合ったら終わり
# for _ in range(N + 1):
while r - l >= 0:
    m = (r + l) // 2  # 必ず真ん中を指す
    if r == X:
        ans += nP
        break
    elif l == X:
        break

    nP = nP // 2
    if X == m:
        ans += nP + 1
        break
    if X > m:
        # Bの数を足す
        ans += nP + 1
        l = m + 1
        r -= 1
    else:
        l += 1
        r = m - 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:
    if x<1:
      return 0
    else:
      return 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])
print(f(N,X))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
def func(N,X):
    if N == 0:
        return 1
    elif X == 1:
        return 0
    elif 2 <= X <= 2**(N+1) -2:
        return func(N-1,X-1)
    elif X == 2**(N+1)-1:
        return 2**N
    elif 2**(N+1) <= X <= 2**(N+2)-4:
        return 2**N + func(N-1,X-(2**(N+1)-1))
    else:
        return 2*(2**N)-1
print(func(N,X))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(l):
    if l == 0:
        return 1, 1
    x, y = solve(l - 1)
    return x * 2 + 1, y * 2 + 3


def main():
    N, X = [int(x) for x in input().split()]
    b = []
    for y in range(51):
        b.append(solve(y))

    # print(b)
    ans = 0
    for y in range(N, -1, -1):
        if X >= b[y][1] * 2 + 1:
            X -= b[y][1]
            X -= b[y][1]
            ans += b[y][0]
            ans += b[y][0]
            ans += 1
        elif X >= b[y][1] + 1:
            X -= b[y][1]
            ans += b[y][0]
            ans += 1
            X -= 2
        elif X >= b[y][1]:
            X -= b[y][1]
            ans += b[y][0]
        else:
            X -= 1

    print(ans)




if __name__ == '__main__':
    main()

Submission status: Accepted

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


def f(N, X):
    result = 0

    if X >= 1:
        X -= 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
        result += 1
    else:
        return result

    if X >= 2 ** ((N - 1) + 2) - 3:
        X -= 2 ** ((N - 1) + 2) - 3
        result += 2 ** ((N - 1) + 1) - 1
    else:
        return result + f(N - 1, X)

    if X >= 1:
        X -= 1
    else:
        return result

    return result


print(f(N, X))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
a = [1]
p = [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)
    elif X == 2+a[N-1]:
        return p[N-1]+1
    elif 2+a[N-1] < X <= 2+2*a[N-1]:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])
    elif X == 3+2*a[N-1]:
        return 2*p[N-1] +1

print(f(N,X))

Submission status: Accepted

Solution code:
from itertools import accumulate
N, X = map(int, input().split())
P = list(accumulate([1]*(N+1), lambda acc,x: acc*2+1))
A = list(accumulate([1]*(N+1), lambda acc,x: acc*2+3))
ans = 0
for n in range(N-1, -1, -1):
    if X >= 2 * A[n] + 2:
        X -= 2 * A[n] + 2
        ans += 2 * P[n] + 1
    elif X >= A[n] + 2:
        X -= A[n] + 2
        ans += P[n] + 1
    elif X >= A[n] + 1:
        X -= A[n] + 1
        ans += P[n]
    elif X >= 1:
        X -= 1
    else:
        break
print(ans)