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 solve(level, eat_layer, all_layers, meat):
    if eat_layer == 1:
        return 0 if level > 0 else 1
    elif eat_layer <= all_layers[level - 1] + 1:
        return solve(level - 1, eat_layer - 1, all_layers, meat)
    elif eat_layer == all_layers[level - 1] + 2:
        return 1 + meat[level - 1]
    elif eat_layer <= 2 + 2 * all_layers[level - 1]:
        return 1 + meat[level - 1] + solve(level - 1, eat_layer - 2 - all_layers[level - 1], all_layers, meat)
    elif eat_layer == 3 + 2 * all_layers[level - 1]:
        return 2 * meat[level - 1] + 1


def main():
    level, eat_layer = map(int, input().split())
    level_layer = [1]
    meat = [1]
    for _ in range(level):
        level_layer.append(2 * level_layer[-1] + 3)
        meat.append(2 * meat[-1] + 1)
    print(solve(level, eat_layer, level_layer, meat))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

piece = [1]
meet  = [1]
for _ in range(n):
  piece.append(piece[-1]*2 +3)
  meet.append(meet[-1]*2+1)
  
ans = 0
i = n
while x:
  if x > (piece[i]+1)//2:
    ans += meet[i]//2+1
    x -= piece[i]//2+1
    i -= 1
  elif x== (piece[i]+1) //2:
    ans += meet[i]//2+1
    x = 0
  else:
    i -= 1
    x -= 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
n,x=map(int,input().split())
l=[0]*(n+1)
c=[0]*(n+1)
c[0]=l[0]=1
for i in range(1,n+1):
  l[i]=l[i-1]*2+3
  c[i]=c[i-1]*2+1
def check(r,t):
  if r==0 and t>0:
    return 1
  elif r==0:
    return 0
  elif t<=l[r-1]+1:
    return check(r-1,t-1)
  else:
    return check(r-1,t-l[r-1]-2)+c[r-1]+1
print(check(n,x))

Submission status: Accepted

Solution code:

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

    L = [0 for _ in range(n + 1)] # 総枚数
    P = [0 for _ in range(n + 1)] # パティ枚数
    L[0] = 1
    P[0] = 1

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

    def search(l, r):
        if l == 0:
            return 1
        if r == 1:
            return 0

        r -= 1 # パンを食べる
        if L[l - 1] > r:
            return search(l - 1, r)
        if L[l - 1] == r:
            return P[l - 1]
        if L[l - 1] + 1 == r:
            return 1 + P[l - 1]

        r -= L[l - 1] + 1 # 下半分を食べる
        if L[l - 1] > r:
            return search(l - 1, r) + 1 + P[l - 1]
        if L[l - 1] == r or L[l - 1] + 1 == r:
            return 1 + 2 * P[l - 1]
        
    print(search(n, x))


submit()

Submission status: Accepted

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

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

def f(N, X): ## レベルＮバーガーのＸ層目までのパティの数
    if N==0:
        return 1
    
    if X==1:
        return 0
    elif 2<=X<=num[N-1]+1:
        return f(N-1, X-1)
    elif X==num[N-1]+2:
        return pati[N-1]+1
    elif num[N-1]+3<=X<=2*num[N-1]+2:
        return pati[N-1]+1 + f(N-1, X-num[N-1]-2)
    else:
        return pati[N]
print(f(N, X))

Submission status: Accepted

Solution code:
def solve(L, x):
    if L == 0:
        return 1
    elif x == 1 or x == 0:
        return 0
    elif (2**(L+2)-3)//2 >= x >= 2:
        return solve(L-1, x-1)
    elif x == (2**(L+2)-3)//2 +1:
        return (2**(L+1)-1)//2+1
    elif (2**(L+2)-3)//2+2 <= x <= (2**(L+2)-3):
        return 2**(L+1)-1-solve(L,(2**(L+2)-3)-x)

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

Submission status: Accepted

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

S, P = [1], [1]
for i in range(n):
    S.append(S[i]*2+3)
    P.append(P[i]*2+1)


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


print(f(n, x))

Submission status: Accepted

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

n_patties = {0:1}
l_burgur = {0:1}
for i in range(N):
  n_patties[i+1] = n_patties[i]*2+1
  l_burgur[i+1] = l_burgur[i]*2+3 

def cnt_patty(level,x):
  if x == l_burgur[level]:
    return n_patties[level]
  elif l_burgur[level-1] + 2 < x:
    return n_patties[level-1] + 1 + cnt_patty(level-1,x-l_burgur[level-1]-2)
  elif l_burgur[level-1] + 2 == x:
    return n_patties[level-1] + 1
  elif 1 < x:
    return cnt_patty(level-1,x-1)
  else:
    return 0

print(cnt_patty(N,X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a,b=[1],[1]
for i in range(50):
    a.append(a[-1]*2+3)
    b.append(b[-1]*2+1)
def paty(l,u):
    if l==0 and u==1:
        return 1
    if u==1:
        return 0
    elif u<a[l]//2+1:
        return paty(l-1,u-1)
    elif u==a[l]//2+1:
        return b[l-1]+1
    elif u<a[l]:
        return b[l-1]+1+paty(l-1,u-a[l]//2-1)
    else:
        return b[l]
print(paty(n,x))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a,b=[1],[1]
for i in range(50):
    a.append(a[-1]*2+3)
    b.append(b[-1]*2+1)
def paty(l,u):
    if l==0 and u==1:
        return 1
    if u==1:
        return 0
    elif u<a[l]//2+1:
        return paty(l-1,u-1)
    elif u==a[l]//2+1:
        return b[l-1]+1
    elif u<a[l]:
        return b[l-1]+1+paty(l-1,u-a[l]//2-1)
    else:
        return b[l]
print(paty(n,x))

Submission status: Accepted

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


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


print(ans(N, X))

Submission status: Accepted

Solution code:
def f(N,X):
    if N==0:
        return 1
    elif X==1:
        return 0
    elif 1<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==A[N]:
        return P[N]

#入力
from sys import stdin
readline=stdin.readline
N,X=map(int,readline().split())

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

print(f(N,X))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
l = [[1,1],[5,3]]

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

ans = 0
for i in range(n-1,0,-1):
    if x >= l[i][0]+2:
        ans += l[i][1]+1
        x -= l[i][0]+2
    else:
        x -= 1

if x > 0:
    b = [0,1,1,1,0]
    ans += b[:x].count(1)
print(ans)

Submission status: Accepted

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

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

def f(n, x):
    c = PB[n] // 2 + 1
    if x == 0:
        return 0
    if x == PB[n]:
        return P[n]
    if x < c:
        return f(n - 1, x - 1)
    else:
        return P[n - 1] + 1 + f(n - 1, x - c)

print(f(n, x))

Submission status: Accepted

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

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

def mid(n):
    return (C[n]-1)//2


def f(n,l):
    if n==0:
        return 1
        
    if l==mid(n):
        return f(n-1,mid(n-1)*2)+1
    elif l==mid(n)*2:
        return f(n-1,mid(n-1)*2)*2+1
    elif l==0:
        return 0
    elif 0<l and l<mid(n):
        return f(n-1,l-1)
    else:
        return f(n-1,2*mid(n-1))+1+f(n-1,l-mid(n)-1)
print(f(n,x-1))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,x = list(map(int,input().split()))

#n=1~50までのパティの数と、バーガーの長さ
l = [(1,1)]
for i in range(1,51):
    l.append((l[-1][0]*2+1,l[-1][1]*2+3))

def calc(dim,eat):
    ret = 0
    if eat==0:
        return 0
    elif dim==0:
        return 1
    else:
        if eat < l[dim][0]:
            ret+=calc(dim-1,eat-1)
        elif eat==l[dim][1]:
            return l[dim][0]
        else:
            ret+=(l[dim-1][0]+1+calc(dim-1,eat-l[dim][0]))
    return ret

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 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        # B(N-1) | P(N-1)B の真ん中のパティの前までの範囲がわかればいい場合
        # Xから先頭のバンの数を引いて、N-1の先頭からX-1までの数を数えるために再帰で呼び出す
        return f(N-1,X-1)
    else:
        # 真ん中のパティ以上の枚数を数える必要がある場合
        # 一つ前のレベルのパティの数 + 真ん中のパティ + f(レベル-1, この関数呼び出しで知りたいトータルの枚数-2(先頭のバンと真ん中のパティ)-一つ前のレベルのハンバーガーのトータルの枚数)
        # X-2-a[N-1] → X - (B(N-1)P)|ここから後ろの先頭からK枚を数えるために再帰で呼び出す
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N,X))

Submission status: Accepted

Solution code:
def solve(n, x):
    layers = 2 ** (n + 1) - 3  # レベルn-1バーガーの層の数
    patties = 2 ** n - 1    # レベルn-1バーガーのパティの数
    if x == 0:
        ans = 0
    elif x <= layers + 1:
        ans = solve(n - 1, x - 1)
    elif x <= 2 * layers + 2:
        ans = patties + 1 + solve(n - 1, x - layers - 2)
    else:
        ans = 2 * patties + 1

    return ans

N, X = [int(x) for x in input().split()]
print(solve(N, X))

Submission status: Accepted

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

def burger(N,X):
  #print(N,X)
  if N == 0 and X == 1:
    return 1
  if X == 0:
    return 0
  twopow = pow(2,N)
  if X == 4*twopow-3:
    return 2*twopow-1
  if X > 2*twopow-2:
    return twopow + burger(N-1,X-2*twopow+1)
  elif X <= 2*twopow-2:
    return burger(N-1,X-1)

print(burger(N,X))

Submission status: Accepted

Solution code:
# レベルiバーガーの層数は 2^(i+2) - 3
def layers(i):
    return 2 ** (i + 2) - 3

# レベルiバーガーのパティ数は 2^(i+1) - 1
def patties(i):
    return 2 ** (i + 1) - 1

def solve(n, x):
    layers = 2 ** (n + 1) - 3  # レベルn-1バーガーの層の数
    patties = 2 ** n - 1    # レベルn-1バーガーのパティの数
    if x == 0:
        ans = 0
    elif x < layers + 1:
        ans = solve(n - 1, x - 1)
    elif x == layers + 1:
        ans = patties
    elif x == layers + 2:
        ans = patties + 1
    elif x < 2 * layers + 2:
        ans = patties + 1 + solve(n - 1, x - layers - 2)
    else:
        ans = 2 * patties + 1
    return ans

N, X = [int(x) for x in input().split()]
print(solve(N, X))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

numP_N = [0]*N
numPB_N = [0]*N
numP_N[0] = 3
numPB_N[0] = 5
for i in range(1,N):
    numP_N[i] = numP_N[i-1] * 2 + 1
    numPB_N[i] = numPB_N[i-1] * 2 + 3

def rec(n, x):
    if n == 1:
        ans_1 = [0,0,1,2,3,3]
        return ans_1[x]

    if x == numPB_N[n-1]:
        return numP_N[n-1]

    elif x > numPB_N[n-2] + 2:
        return numP_N[n-2] + 1 + rec(n-1, x-numPB_N[n-2] - 2)

    elif x == numPB_N[n-2] + 2:
        return numP_N[n-2] + 1

    elif x == numPB_N[n-2] + 1:
        return numP_N[n-2]

    elif x < numPB_N[n-2] + 1:
        return rec(n-1, x-1)

print(rec(N,X))

Submission status: Accepted

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


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:
import sys
sys.setrecursionlimit(10**9)

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

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

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

def solve(n, x):
  if x <= 0:
    return 0
  num = num_layer(n-1) + 2
  if x == num*2 - 1:
    return num_p(n)
  elif x == num:
    return num_p(n-1) + 1
  elif x < num:
    return solve(n-1, x-1) # 1番下のバンを食べる
  else:
    return solve(n-1, x-num) + num_p(n-1) + 1

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


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 - (a[N-1]+2))

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


def p(level):
    if level == 0:
        return 1
    return 2*p(level-1)+1


def a(level):
    if level == 0:
        return 1
    return 2*a(level-1)+3


def f(level, x):
    if level == 0:
        return 1
    elif x == 1:
        return 0
    else:
        if 1 < x <= 1 + a(level-1):
            return f(level-1, x-1)
        else:
            if x == 2 + a(level-1):
                return 1 + p(level-1)
            elif 2+a(level-1) < x <= 2 + 2*a(level-1):
                return 1 + p(level-1)+f(level-1, x-2-a(level-1))
            elif x == 3 + 2*a(level-1):
                return 1 + 2*p(level-1)


print(f(n, x))

Submission status: Accepted

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


def p(level):
    if level == 0:
        return 1
    return 2*p(level-1)+1


def a(level):
    if level == 0:
        return 1
    return 2*a(level-1)+3


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 = (int(i) for i in input().split())  
L = [1]
P = [1]

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

def count(x,n):
  if n == 0:
    return 0 if x <= 0 else 1
  elif x <= L[n-1] + 1:
    return count(x-1, n-1)
  else:
    return P[n-1] + 1 + count(x-(L[n-1]+2),n-1)

#print(L,P)
print(count(X, N))

Submission status: Accepted

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

position = 2**(n+2)-3
result = 0
while x > 0:
    position = (position-1)//2
    if x == position*2+1:
        result += position + 1
        x = 0
    elif x == position+1:
        result += position//2 + 1
        x = 0
    elif x > position:
        x -= position
        result += position//2+1
    x -= 1
    position -= 1
print(result)

Submission status: Accepted

Solution code:
# 解説AC

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

# 層数、パティ数をA, Pに格納する
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 <= 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:
# -*- coding: utf-8 -*-
import sys
import math

N,X = list(map(int, input().rstrip().split()))
#-----

## レベルnバーガーの、層の数
def material(n):
    return 2**(n+2)-3

## レベルnバーガーの、Pattyの数
def patty(n):
    return 2**(n+1)-1

cnt=0
while N > 0:
    half = material(N) // 2 + 1
    
    if X == half:
        cnt += patty(N-1) + 1
        break
    elif X == 1:
        break
    elif X > half:
        cnt += patty(N-1) + 1
        N -= 1
        X -= half
    elif 1 < X < half:
        N -= 1
        X -= 1

    ## last    
    if N == 0:
        cnt += 1

print(cnt)

Submission status: Accepted

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

ans=[]
if X==1:
    print(0)
    exit()
def f(n,x):
    #print(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]
a=[1]
for i in range(1,1+N):
    b=2*p[i-1]+1
    p.append(b)
    c=2*a[i-1]+3
    a.append(c)

ans=[]
if X==1:
    print(0)
    exit()
def f(n,x):
    #print(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=list(map(int,input().split()))

def rec(lev,x):
    bottom=1
    center=2**(lev+1)-1
    top=2**(lev+2)-3


    if x>center:
        if top==x:
            return 2**(lev+1)-1
        return 2**lev+rec(lev-1,x-center)
    elif x==center:
        return 2**lev
    else:
        if bottom==x:
            return 0
        
        return rec(lev-1,x-1)

print(rec(n,x))

Submission status: Accepted

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

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

def f(m, y):
  if m == 0:
    return 1
  if sizes[m] - 1 <= y:
    return nums[m]
  ret = 0
  y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
    y -= sizes[m - 1]
  if y > 0:
    ret += 1
    y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
  return ret

print(f(n, x))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(20000)

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

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

def f(m, y):
  if m == 0:
    return 1
  if sizes[m] - 1 <= y:
    return nums[m]
  ret = 0
  y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
    y -= sizes[m - 1]
  if y > 0:
    ret += 1
    y -= 1
  if y > 0:
    ret += f(m - 1, min(y, sizes[m - 1]))
  return ret

print(f(n, x))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
 
N, X = [int(x) for x in input().split()]
# P,B
L = [1]

#P
P = [1]

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

ans = 0
# idx = N
while True:
    if L[N] == X:
        ans += P[N]
        print(ans)
        break
    elif L[N] - 1 == X:
        ans += P[N]
        print(ans)
        break
    elif 2 + L[N - 1] <= X:
        ans += 1 + P[N - 1]
        X -= 2 + L[N - 1]
        if X == 0:
            print(ans)
            break
    elif 1 + L[N - 1] == X:
        ans += P[N - 1]
        print(ans)
        break
    elif X == 1:
        print(ans)
        break
    else:
        X -= 1
    N -= 1

Submission status: Accepted

Solution code:
# Lバーガーのパティの数はL-1バーガーのパティ*2 + 1枚
# Lバーガーのバンの数はL-1バーガーのバン*2 + 2枚
n, x = map(int, input().split())
P = [1]
B = [0]
for _ in range(n):
    P.append(P[-1]*2+1)
    B.append(B[-1]*2+2)


# レベルLバーがの下からx層に含まれるパティの数
# B (L-1) P (L-1) B
def dfs(L, x):
    
    if L == 0:  # レベル0バーガーはパティ1枚のみ
        return 1
      
    l = P[L]+B[L]  # 厚さはP[i]+B[i](必ず奇数)
    mid = l//2 + 1
    
    if x == mid:  # どのレベルでも真ん中はパティ
        return 1 + P[L-1]
    elif x == 1:  # どのレベルでも一番下はバン
        return 0
    elif x == l:
        return 1 + P[L-1]*2        
    elif x < mid:
        return dfs(L-1, x-1) 
    elif x > mid:
        return dfs(L-1, x-1-(P[L-1]+B[L-1])-1) + 1 + P[L-1]

print(dfs(n, x))

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n, x = LI()
p = [0] * n
a = [0] * n
a[0] = p[0] = 1
for i in range(1, n):
    a[i] = 2 * a[i - 1] + 3
    p[i] = 2 * p[i - 1] + 1


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

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

ans=0
end=[0,1,2,3,3]

for i in range(n):
    hambergar=[1,1+length[i+1],2+length[i+1],2+2*length[i+1],3+2*length[i+1]]
    if i==n-1:
        ans+=end[x-1]
    else:
        if hambergar[0]<x and x<hambergar[2]:
            x-=1
        
        elif hambergar[2]<x and x<hambergar[4]:
            ans+=patty[i+1]+1
            x-=hambergar[2]
        
        elif hambergar[2]==x:
            ans+=patty[i+1]+1
            break

        elif hambergar[4]==x:
            ans+=patty[i]
            break
        
        elif hambergar[4]<x or x<=1:
            break

print(ans)

Submission status: Accepted

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

ans = 0
s = [(X, N)]
while s:
    x, n = s.pop()
    if n==0:
        ans += x!=0
    if x:
        a = q[n-1] + 2
        b = p[n-1] + 1

        if x >= a:
            ans += b
            s += [(x-a, n-1)]
        else:
            s += [(x-1, n-1)]

print(ans)

Submission status: Accepted

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

ans = 0
s = [(X, N)]
while s:
    x, n = s.pop()
    if n==0:
        if x:
            ans += 1
    if x:
        a = q[n-1] + 2
        b = p[n-1] + 1

        if x >= a:
            ans += b
            s += [(x-a, n-1)]
        else:
            s += [(x-1, n-1)]

print(ans)

Submission status: Accepted

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

ans = 0
s = [(X, N)]
while s:
    x, n = s.pop()
    if n==0:
        if x:
            ans += 1
    if x:
        a = q[n-1] + 2
        b = p[n-1] + 1

        if x > a:
            ans += b
            s += [(x-a, n-1)]
        elif x == a:
            ans += b
        else:
            s += [(x-1, n-1)]

print(ans)

Submission status: Accepted

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

ans = 0
s = [(X, N)]
while s:
    x, n = s.pop()
    if n==0:
        if x:
            ans += 1
        continue
    if x==0:
        continue
    
    a = q[n-1] + 2
    b = p[n-1] + 1

    if x > a:
        ans += b
        s.append((x-a, n-1))
    elif x == a:
        ans += b
    else:
        s.append((x-1, n-1))

print(ans)

Submission status: Accepted

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

ans = 0
def search(x, n):
    global ans
    if n==0:
        if x:
            ans += 1
        return
    if x==0:
        return
    
    a = q[n-1] + 2
    b = p[n-1] + 1

    if x > a:
        ans += b
        search(x-a, n-1)
    elif x == a:
        ans += b
    else:
        search(x-1, n-1)

search(X, N)
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache()
def f(n):
    if n==0:
        return 1
    return 2*f(n-1)+1

@lru_cache()
def g(n):
    if n==0:
        return 1
    return 2*g(n-1)+3

N, X = map(int, input().split())
total = [g(i) for i in range(N+1)]
p = [f(i) for i in range(N+1)]
ans = 0

def search(x, n):
    global ans
    if n==0:
        if x:
            ans += 1
        return
    if x==0:
        return
    if x > total[n-1] + 2:
        ans += p[n-1] + 1
        search(x-(2 + total[n-1]), n-1)
    elif x == total[n-1] + 2:
        ans += p[n-1] + 1
    else:
        search(x-1, n-1)

search(X, N)
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache

@lru_cache()
def f(n):
    if n==0:
        return 1
    return 2*f(n-1)+1

@lru_cache()
def g(n):
    if n==0:
        return 1
    return 2*g(n-1)+3

N, X = map(int, input().split())
total = [g(i) for i in range(N+1)]
p = [f(i) for i in range(N+1)]

ans = 0

def search(x, n):
    global ans
    if n==0 and x:
        ans += 1
        return
    if x > total[n-1] + 2:
        ans += p[n-1] + 1
        if n and x:
            search(x-(2 + total[n-1]), n-1)
    elif x == total[n-1] + 2:
        ans += p[n-1] + 1
    else:
        if n and x:
            search(x-1, n-1)

search(X, N)
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)
#print(a)

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

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())
As = [1]
Ps = [1]
for i in range(N):
    As.append(As[i] * 2 + 3)
    Ps.append(Ps[i] * 2 + 1)

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

    med = (As[n] + 1) // 2
    if x < med:
        return f(n - 1, x - 1)
    elif x == med:
        return Ps[n - 1] + 1
    elif x > med:
        return Ps[n - 1] + 1 + f(n - 1, x - med)

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

# def make_burger(s, count):
#     # count += 1
#     # print(s)
#     if count == N:
#         return s
#     return make_burger('B' + s + 'P' + s + 'B', count + 1)

# print(make_burger('P', 0))

Submission status: Accepted

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

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


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

print(f(N, X))

Submission status: Accepted

Solution code:
#115_D
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>0 else 0
    elif x<=1+a[n-1]:
        return f(n-1,x-1)
    else:
        return p[n-1]+1+f(n-1,x-2-a[n-1])
    
print(f(N,X))

Submission status: Accepted

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

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

print(F(n,x))

Submission status: Accepted

Solution code:
from functools import lru_cache as cache

@cache(maxsize=None)
def t(n):
    return 1 if n == 0 else t(n - 1) * 2 + 3

@cache(maxsize=None)
def p(n):
    return 1 if n == 0 else p(n - 1) * 2 + 1

f = lambda n, x: (0 if x <= 0 else 1) if n == 0 else f(n - 1, x - 1) if x <= 1 + t(n - 1) else p(n - 1) + 1 + f(n - 1, x - 2 - t(n - 1))

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

Submission status: Accepted

Solution code:
from functools import lru_cache as cache

@cache(maxsize=None)
def t(n):
    return 1 if n == 0 else t(n - 1) * 2 + 3

@cache(maxsize=None)
def p(n):
    return 1 if n == 0 else p(n - 1) * 2 + 1

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

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

print(f(N, X))

Submission status: Accepted

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

T, P = [1], [1]
for i in range(N):
    T.append(T[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 + T[N - 1]:
        return f(N - 1, X - 1)
    else:
        return P[N - 1] + 1 + f(N - 1, X - 2 - T[N - 1])

print(f(N, X))

Submission status: Accepted

Solution code:
def main():
  n,x=map(int,input().split())
  from functools import lru_cache
  
  @lru_cache()
  def dfs(n,l,x): #レベルnバーガーで下からx番目までのパティの数
    if n==0:
      return 1
    else:
      t=(l-3)//2
      if x==1:
        return 0
      elif x<=l//2:
        return dfs(n-1,t,x-1)
      elif x==l//2+1:
        return dfs(n-1,t,x-2)+1
      else:
        return dfs(n-1,t,t)+1+dfs(n-1,t,x-t-2)
  print(dfs(n,2**(n+2)-3,x))
if __name__=='__main__':
  main()