Problem:


Score : 400 points

Problem Statement

In some other world, today is Christmas.

Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:

A level-0 burger is a patty.

A level-L burger (L \geq 1) is a bun, a level-(L-1) burger, a patty, another level-(L-1) burger and another bun, stacked vertically in this order from the bottom.

For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.

The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?

Constraints

1 \leq N \leq 50

1 \leq X \leq ( the total number of layers in a level-N burger )

N and X are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.

Sample Input 1

2 7

Sample Output 1

4

There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB).

Sample Input 2

1 1

Sample Output 2

0

The bottom-most layer of a level-1 burger is a bun.

Sample Input 3

50 4321098765432109

Sample Output 3

2160549382716056

A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.



Sample input:
2 7


Sample output:
4

Submission status: Accepted

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

dp = [1]*(n+1)
res = 0

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

for j in range(n,1,-1):
    if dp[j] ==x:
        res += (dp[j]+1) //2
        x =0        
    elif dp[j-1]+2 <= x :
        res += 1 + (dp[j-1]+1)//2
        x -= dp[j-1]+2
    elif dp[j-1]+1 ==x:
        res += (dp[j-1]+1)//2
        x = 0
    else:
        x -=1
    
    if x ==0:
        break
        
if x ==5:
    res += 3
elif x ==0:
    pass
else:
    res +=x-1

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
#coding: utf-8

from collections import defaultdict

N, X = (int(x) for x in input().split())

memo = {}

def size_lv(lv):
    if lv == 0:
        return 1
    if lv not in memo:
        memo[lv] = size_lv(lv-1) * 2 + 3
    return memo[lv]

memo2 = {}
def num_pty(lv, X):
    if (lv, X) in memo2:
        return memo2[(lv, X)]
    if X == 0:
        return 0

    if lv == 0:
        memo2[(lv, X)] = 1
        return memo2[(lv, X)]

    prevSize = size_lv(lv-1)
    if X <= prevSize+1:
        memo2[(lv, X)] = num_pty(lv-1, X-1)
        return memo2[(lv, X)]
    
    if X == prevSize + 2:
        memo2[(lv, X)] = num_pty(lv-1, prevSize) + 1
        return memo2[(lv, X)]
    
    memo2[(lv, X)] = num_pty(lv-1, prevSize) + 1 + num_pty(lv-1, min(X-prevSize-2, prevSize))
    return memo2[(lv, X)]
    
print(num_pty(N, X))

# BBPPPBPBPPPBB
# BPPPB

Submission status: Accepted

Solution code:
# レベルLのN番目
def solve(L,N):
    if L == 0:
        return 1
    if N == 1:
        return 0
    elif N <= 2**(L+1)-2:
        return solve(L-1,N-1)
    elif N == int(2**(L+1)-1):
        return 2**L
    return solve(L-1,N-2**(L+1)+1)+2**L
    

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

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
c=0
def p(n):
  return 2*(2**n)-1
def f(n):
  return 4*(2**n)-3

c=0
for i in range(n,0,-1):
  if x:
    x-=1
  if x>=f(i-1):
    x-=f(i-1)
    c+=p(i-1)
    if x:
      x-=1
      c+=1
      if x>=f(i-1):
        x-=f(i-1)
        c+=p(i-1)
        if x:
          x-=1
print(c)

Submission status: Accepted

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

ans = 0
for i in range(N, -1, -1):
    if X < 2**(i + 1) - 1:
        X -= 1
    elif X > 2 ** (i + 1) - 1:
        X -= 2 ** (i + 1) - 1
        ans += 2 ** i
    else:
        ans += 2 ** i
        break
    if X == 0:
        break
    #print(X, ans)


print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def L(N):
    if N == 0:
        return 1
    return 3 + 2 * L(N-1)
def P(N):
    if N == 0:
        return 1
    return 1 + 2 * P(N-1)

def A(N,X):
    res = 0
    if N == 0:
        return 1
    if X == 1:
        return 0
    if 1 < X <= L(N-1) + 1:
        res = A(N-1,X-1)
    elif L(N-1) + 2 == X:
        res = 1 + P(N-1)
    elif L(N-1) + 2 < X <= 2 * L(N-1) + 2:
        res = 1 + P(N-1) + A(N-1,X-(2+L(N-1)))
    elif 2 * L(N-1) + 3 == X:
        res = 1 + 2 * P(N-1)
    return res

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main(n, x, ans):
  global X
  global l
  if n == 0:
    return ans+1
  elif x==1:
    return ans
  elif x==2*l[n]-1:
    return ans+2*l[n-1]+1
  elif x == l[n]:
    return main(n-1, x-2, ans+1)
  elif x < l[n]:
    return main(n-1, x-1, ans)
  else:
    return main(n-1, x-2*l[n-1]-1, ans+l[n-1]+1)
  
a = main(N, X, 0)
print(a)

Submission status: Accepted

Solution code:
def f(L, x):
    if L == 0:
        return 0 if x <= 0 else 1
    if x <= total[L - 1] + 1:
        return f(L - 1, x - 1)
    else:
        return patties[L - 1] + 1 + f(L - 1, x - total[L - 1] - 2)


N, X = map(int, input().split())
total = [1]
patties = [1]
for i in range(50):
    total.append(total[-1] * 2 + 3)
    patties.append(patties[-1] * 2 + 1)
print(f(N, X))

Submission status: Accepted

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

f_dict = {
  0: 1
}
def f(n):
  if f_dict.get(n):
    return f_dict.get(n)
  return (3 + f(n-1) * 2)


patty_dict = {
  0: 1
}
def total_patty(n):
  if patty_dict.get(n):
    return patty_dict.get(n)
  return (1 + 2 * total_patty(n - 1))

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

print(count_patty(n, x))

Submission status: Accepted

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

maisu=[0]*50
pate=[0]*50
maisu[0]=1
pate[0]=1

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

def solve(l,x):
    if l==0:
        return 1
    if x<=1:
        return 0

    if x<=1+maisu[l-1]:
        return solve(l-1,x-1)
    if x==2+maisu[l-1]:
        return pate[l-1] + 1

    return pate[l-1] + 1 + solve(l-1,x-2-maisu[l-1])

print(solve(n,x))

Submission status: Accepted

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

t = [1]
p = [1]

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

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

print(pathi(n, x))

Submission status: Accepted

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

t = [1]
p = [1]

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

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

print(pathi(n, x))

Submission status: Accepted

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

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

h = [1]
p = [1]

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

def bug(l, y):
    if l == 0:
        return 0 if y <= 0 else 1
    
    mid = (h[l] + 1) // 2
    if y < mid:
        return bug(l - 1, y - 1)
    elif y == mid:
        return p[l - 1] + 1
    elif y > mid:
        return p[l - 1] + 1 + bug(l - 1, y - mid)
    
print(bug(N, X))

Submission status: Accepted

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

def rec(m, y):
    if y == 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2
    if h < y:
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)
print(rec(n, x))

Submission status: Accepted

Solution code:
memo1 = {}
def f(i):
    if i==0:
        return 1
    if i in memo1:
        return memo1[i]
    memo1[i] = 2*f(i-1)+3
    return memo1[i]
memo2 = {}
def g(i):
    if i==0:
        return 1
    if i in memo2:
        return memo2[i]
    memo2[i]=2*g(i-1)+1
    return memo2[i]
N,X = map(int,input().split())
cnt = 0
while X>0 and N>0:
    if X==f(N):
        cnt += g(N)
        X -= f(N)
    elif X>=f(N-1)+2:
        cnt += 1+g(N-1)
        X -= f(N-1)+2
    else:
        X -= 1
    N -= 1
cnt += X
print(cnt)

Submission status: Accepted

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

p = [0] * -~n
l = [0] * -~n

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

# バーガーの長さは奇数


def rec(m, y):
    if y == 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2  # レベルmの半分より左側の長さ
    if h < y:  # 真ん中含む
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))

Submission status: Accepted

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

p = [0] * -~n
l = [0] * -~n

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

# バーガーの長さは奇数


def rec(m, y):
    if y <= 0:
        return 0
    if m == 0:
        return 1
    h = l[m] // 2  # レベルmの半分より左側の長さ
    if h < y:  # 真ん中含む
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))

Submission status: Accepted

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

p = [0] * -~n
l = [0] * -~n

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

# バーガーの長さは奇数


def rec(m, y):
    if y <= 0:
        return 0
    if m == 0:
        return 1 if y > 0 else 0
    h = l[m] // 2  # レベルmの半分より左側の長さ
    if h < y:  # 真ん中含む
        return 1 + p[m - 1] + rec(m - 1, y - h - 1)
    else:
        return rec(m - 1, y - 1)


print(rec(n, x))

Submission status: Accepted

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

Submission status: Accepted

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

def rec(level, K):
    if level == 0:
        return 1
    if K == 1:
        return 0
    elif K <= L[level-1] + 1:
        return rec(level-1, K-1)
    elif K == L[level-1] + 2:
        return S[level-1] + 1
    elif K <= L[level-1] * 2 + 2:
        return rec(level-1, K - L[level-1] - 2) + S[level-1] + 1;
    else:
        return S[level-1] * 2 + 1

print(rec(N, X))

Submission status: Accepted

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

Submission status: Accepted

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

f=[1]
p=[1]

for n in range(N):
    f.append(2*f[n]+3)
    p.append(2*p[n]+1)

def get_p(N,X):
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 1
    if X == 1:
        return 0
    elif X > 1 and X <= f[N-1] + 1:
        return get_p(N-1,X-1)
    elif X == f[N-1] + 2:
        return p[N-1]+1
    elif X > f[N-1] + 2 and X <= 2*f[N-1] + 1: 
        return p[N-1] + 1 + get_p(N-1,X-(f[N-1]+2))
    else:
        return p[N]
    
print(get_p(N,X))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,x = list(map(int, input().split()))
l = [None]*(n+1)
ps = [None]*(n+1)
v = 1
vp = 1
for i in range(n+1):
    l[i] = v
    ps[i] = vp
    v = 2*v + 3
    vp = 2*vp + 1
def sub(n,x):
    if n==0:
        if x==1:
            return 1
        else:
            return 0
    if x==1:
        return 0
    elif x==l[n]:
        return ps[n]
    elif x==l[n-1]+2:
        return ps[n-1]+1
    elif x<l[n-1]+2:
        return sub(n-1,x-1)
    else:
        return sub(n-1,x-2-l[n-1]) + ps[n-1] + 1
ans = sub(n,x)
print(ans)

Submission status: Accepted

Solution code:

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

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

    return p[n - 1] + 1 + func(n - 1, x - 2 - a[n - 1])


print(func(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:
        return 1 if x>0 else 0
    else:
        if x>a[n-1]+1:
            return p[n-1]+1+calc(n-1,x-2-a[n-1])
        else:
            return calc(n-1,x-1)
print(calc(n,x))

Submission status: Accepted

Solution code:
a = [1]
b = [1]
for _ in range(50):
    a.append(2 * a[-1] + 3)
    b.append(2 * b[-1] + 1)

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

    if x == 1:
        return 0
    elif x <= a[n-1] + 1:
        return num_of_patties(n-1, x-1)
    elif x == a[n-1] + 2:
        return b[n-1] + 1
    elif x <= 2 * a[n-1] + 2:
        return b[n-1] + 1 + num_of_patties(n-1, x-a[n-1]-2)
    else:
        return b[n]


print(num_of_patties(*[int(i) for i in input().split()]))

Submission status: Accepted

Solution code:
N,X=list(map(int, input().split()))
A=[0]*(N+1)
P=[0]*(N+1)
A[0]=1
P[0]=1

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

def burguer(n,x):
    if x==0:
        return 0
    if x==A[n]:
        return P[n]
    if x<=A[n-1]+1:
        y=burguer(n-1,x-1)
        return y
    else:
        y=burguer(n-1,x-A[n-1]-2)
        return P[n-1]+1+y

print(burguer(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 A(x):
  return pow(2, x+2)-3

def P(x):
  return pow(2, x+1)-1

def f(n, x):
  if n==0:
    return 1
  if n==1:
    return min(x-1, 3)
  if x<=n:
    return 0
  if A(n)//2+1==x:
    return P(n-1)+1
  if A(n)==x:
    return P(n)
  if A(n)//2>=x:
    return f(n-1, x-1)
  return P(n-1)+1+f(n-1, x-A(n)//2-1)

print(f(N, X))

Submission status: Accepted

Solution code:
def examA():
    N = DI()/dec(7)
    ans = N
    print(N)
    return

def examB():
    ans = 0
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    N, X = LI()
    S = [0]*(N+1)
    P = [0]*(N+1)
    S[0] = 1; P[0] = 1
    for i in range(N):
        S[i+1] = S[i]*2 + 3
        P[i+1] = P[i]*2 + 1

    def dfs(n,x):
        if n==0:
            return 0<x
        if x>=S[n-1]+2:
            return 1 + P[n-1] + dfs(n-1,x-2-S[n-1])
        return dfs(n-1,x-1)
    ans = int(dfs(N,X))
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
L, C = [1], [1]
for n in range(1,N+1):
    L.append(2*L[-1]+3)
    C.append(2*C[-1]+1)
C.append(0)
step = 0
res = 0
for i in reversed(range(N+1)):
    if X<=step+L[i]//2:
        step+=1
    elif X>step+L[i]//2+1:
        step += L[i]//2+1
        res += C[i-1]+1
    else:
        res += C[i-1]+1
        break
print(res)

Submission status: Accepted

Solution code:

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

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

def pbx(xx,nn):
#    print(xx,nn)
    if nn==0:
        return 1
    if xx==1:
        return 0
    elif xx<=1+pb[nn-1][0]:
        return pbx(xx-1,nn-1)
    elif xx==2+pb[nn-1][0]:
        return pb[nn-1][1]+1
    elif xx<=2+pb[nn-1][0]*2:
        xxx=pbx(xx-pb[nn-1][0]-2,nn-1)
#        print("xxx1",xxx)
        xxx=pb[nn-1][1]+1+xxx
#        print("xxx2",xxx)
        return xxx
    elif xx==3+pb[nn-1][0]*2:
        return pb[nn][1]
    else:
        print("----------",xx,nn)
        return 0

    
print(pbx(x,n))

Submission status: Accepted

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

def func(m,y):
  if y==0:return 0
  ret=0
  t=4*pow(2,m)-3
  if y>=t-1:
    ret=pow(2,m+1)-1
  elif y==(t-1)//2:
    ret=pow(2,m)-1
  elif y==(t-1)//2+1:
    ret=pow(2,m)
  elif y>(t-1)//2+1:
    ret=pow(2,m)
    ret+=func(m-1,y-(t-1)//2-1)
  else:
    ret=func(m-1,y-1)
  return ret

print(func(n,x))

Submission status: Accepted

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

# レベル0バーガー P
# レベル1バーガー BPPPB
# P[i] = レベルiバーガーのパティの枚数
# B[i] = レベルiバーガーの厚さ

P = [0] * 51
B = [0] * 51

P[0] = 1
B[0] = 1

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

# レベルnバーガーを丸ごと食べたときのパティの枚数を求める
def get_whole_barger(n):
  return P[n]

# レベルnバーガーをx枚目まで食べたときのパティの枚数を求める
def get_patty(n,x):
  if n == 0 or x == 0:
    return P[0]
  if B[n] == x:
    return P[n]
  if x <= 1:
    return 0
  if x <= 1 + B[n - 1]:
    return get_patty(n - 1, x - 1)
  if x <= 2 + B[n - 1]:
    return get_whole_barger(n - 1) + 1
  if x <= 2 + B[n - 1] * 2:
    return get_whole_barger(n - 1) + 1 + get_patty(n - 1, x - 2 - B[n - 1])
  else:
    return get_whole_barger(n - 1) + 1 + get_whole_barger(n - 1)

print(get_patty(N,X))

Submission status: Accepted

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

L = [1]
P = [1]

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

print(f(N, K))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    A = [0] * (N + 1)
    B = [0] * (N + 1)
    A[0] = B[0] = 1
    for i in range(N):
        A[i + 1] = 2 * A[i] + 3
        B[i + 1] = 2 * B[i] + 1

    def rec(i, x):
        if i == 0:
            return 1 if x > 0 else 0
        elif x <= 1 + A[i - 1]:
            return rec(i - 1, x - 1)
        else:
            return B[i - 1] + 1 + rec(i - 1, x - 2 - A[i - 1])

    print(rec(N, X))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

    @lru_cache(maxsize=None)
    def rec1(i):
        if i == 0:
            return 1
        else:
            return 2 * rec1(i - 1) + 1

    @lru_cache(maxsize=None)
    def rec2(i):
        if i == 0:
            return 1
        else:
            return 2 * rec2(i - 1) + 3

    def rec(i, x):
        if x <= 0:
            return 0
        if i == 0:
            return 1

        x -= 1
        ans = 0
        if x > rec2(i - 1):
            x -= rec2(i - 1)
            ans += rec1(i - 1)
        else:
            ans += rec(i - 1, x)
            return ans

        if x > 0:
            x -= 1
            ans += 1
        else:
            return ans

        if x > rec2(i - 1):
            x -= rec2(i - 1)
            ans += rec1(i - 1)
        else:
            ans += rec(i - 1, x)

        return ans

    print(rec(N, X))
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

#############
# Main Code #
#############

# レベルNバーガーの下からX層目まで
N, X = getNM()

# レベルNバーガーの中間地点、全体のサイズ
cnt_burger = [[0 for i in range(2)] for i in range(51)]
cnt_burger[0] = [1, 1]
for i in range(1, 51):
    cnt_burger[i][0] = 1 + cnt_burger[i - 1][1] + 1
    cnt_burger[i][1] = cnt_burger[i][0] + cnt_burger[i - 1][1] + 1

# レベルNバーガーにパティが何枚含まれる？
cnt_patty = [0] * 51
cnt_patty[0] = 1
for i in range(1, 51):
    cnt_patty[i] = 2 * cnt_patty[i - 1] + 1

# レベルNの下からX番目までにパティが何枚含まれるか
# xが大きいのでdpはできない
def count(n, x):
    # レベル0バーガーの場合
    if n == 0 and x == 1:
        return 1

    # バーガーの一番下のパンのみ食べる場合
    if x == 1:
        return 0

    # 中間地点以前のどこかまで食べる場合
    elif 1 < x < cnt_burger[n][0]:
        # レベルn - 1バーガーの下からx - 1層目まで
        return count(n - 1, x - 1)

    # 中間地点まで食べる
    elif x == cnt_burger[n][0]:
        return cnt_patty[n - 1] + 1

    # 中間地点 ~ 最後以前のうちのどこか
    elif cnt_burger[n][0] < x < cnt_burger[n][1]:
        return cnt_patty[n - 1] + 1 + count(n - 1, x - cnt_burger[n][0])

    # 最後
    else:
         return 2 * cnt_patty[n - 1] + 1

print(count(N, X))

Submission status: Accepted

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

def level_n_putty(n):
    if n == 0:
        return 1
    else:
        return 2 * level_n_putty(n-1) + 1

def level_n_hb(n):
    if n == 0:
        return 1
    else:
        return 2 * level_n_hb(n-1) + 3

m = level_n_hb(n)

s = 0
base = 0

while True:
    if x == base + 1:
        if n == 0:
            s += 1
        break
    elif x == base + m:
        s += level_n_putty(n)
        break
    else:
        l = level_n_hb(n-1)
        #print(n, base + l + 2, x)
        if x < base + l + 2:
            base += 1
            n -= 1
            m = l
        elif x == base + l + 2:
            s += 1 + level_n_putty(n-1)
            break
        else:
            base = base + l + 2
            s += 1 + level_n_putty(n-1)
            n -= 1
            m = l

print(s)

Submission status: Accepted

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

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

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

print(f(N, X))

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n + 1):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
while n > 0:
    if x >= slice[n - 1] + 2:
        ans += pate[n - 1] + 1
        x -= slice[n - 1] + 2
    elif x < slice[n - 1] + 2:
        x -= 1
    n -= 1
print(ans + (x > 0))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

# レベルnバーガー
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()
a = [0]*n
p = [0]*n
a[0] = 1
p[0] = 1
for i in range(1, n):
    a[i] = a[i-1]*2 + 3
    p[i] = p[i-1]*2 + 1

print(f(n, x))

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

# レベルnバーガー
def dfs(k):
    global count, ans
    # バン
    count += 1
    if k == 0:
        ans += 1
    elif count < x:
        # レベルn-1バーガー
        if count + b[k-1] > x:
            dfs(k-1)
        else:
            count += b[k-1]
            ans += p[k-1]
        if count < x:
            # パティ
            count += 1
            ans += 1
            if count < x:
                # レベルn-1バーガー
                if count + b[k-1] > x:
                    dfs(k-1)
                else:
                    count += b[k-1]
                    ans += p[k-1]

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

count = 0
ans = 0
dfs(n)
print(ans)

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

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

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
for i in range(n)[::-1]:
    if x >= slice[i] + 2:
        ans += pate[i] + 1
        x -= slice[i] + 2
    elif x < slice[i] + 2:
        x -= 1
print(ans + (x > 0))

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n + 1):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
for i in range(n)[::-1]:
    if x >= slice[i] + 2:
        ans += pate[i] + 1
        x -= slice[i] + 2
    elif x < slice[i] + 2:
        x -= 1
print(ans + (x > 0))

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n + 1):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
while n > 0:
    if x >= slice[n - 1] + 2:
        ans += pate[n - 1] + 1
        x -= slice[n - 1] + 2
    elif x < slice[n - 1] + 2:
        x -= 1
    n -= 1
print(ans + (x > 0))

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n + 1):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
while n * x > 0:
    if x >= slice[n - 1] + 2:
        ans += pate[n - 1] + 1
        x -= slice[n - 1] + 2
    elif x < slice[n - 1] + 2:
        x -= 1
    n -= 1
print(ans + (x > 0))

Submission status: Accepted

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

pate, slice = [1], [1]
for _ in range(n + 1):
    pate.append(2 * pate[-1] + 1)
    slice.append(2 * slice[-1] + 3)

ans = 0
while n > 0 and x > 0:
    if x >= slice[n - 1] + 2:
        ans += pate[n - 1] + 1
        x -= slice[n - 1] + 2
    elif x < slice[n - 1] + 2:
        x -= 1
    n -= 1
print(ans + (x > 0))