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 count_p(x, n):
    y = 0
    i = n
    while(True):
        if i == 0:
            return 0
        xx = x - (n - i) + 3 - 2 ** (i + 1)
        if xx >= 0:
            y = 2 ** i - 1
            if xx > 0:
                y += count_p(xx - 1, i) + 1
            break
        else:
            i -= 1
    return y

n, x = map(int, input().split())
ans = count_p(x, n + 1)
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(1, n + 1):
    A[i] = A[i - 1] * 2 + 3
    P[i] = P[i - 1] * 2 + 1

c = 0
for i in list(range(n+1))[::-1]:
    if i == 0:
        c += 1

    elif x == 1:
        break

    elif x <= A[i - 1] + 1:
        x -= 1

    elif x == A[i - 1] + 2:
        c += P[i - 1] + 1
        break

    elif x <= A[i] - 1:
        c += P[i - 1] + 1
        x -= A[i - 1] + 2

    elif x == A[i]:
        c += P[i]
        break

print(c)

Submission status: Accepted

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

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


def pate(m, y):
    if m == 0:
        return 1
    else:
        c = 0

        if y >= 1:
            y -= 1

        if y >= 1:
            if y >= A[m - 1]:
                y -= A[m - 1]
                c += P[m - 1]
            else:
                c += pate(m - 1, y)
                y = 0

        if y >= 1:
            y -= 1
            c += 1

        if y >= 1:
            if y >= A[m - 1]:
                y -= A[m - 1]
                c += P[m - 1]
            else:
                c += pate(m - 1, y)
                y = 0

        if y >= 1:
            y -= 1

        return c


print(pate(n, x))

Submission status: Accepted

Solution code:
import numpy as np

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


def inputList():
	a=list(map(int,input().split()))
	return a

def multisort(li,index):
	return sorted(li,key=lambda x: x[index])

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np

# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
N, X = [int(x) for x in stdin.readline().rstrip().split()]


def func(n, x):
  # 動的計画法?
  if x==0:
    return 0
  elif x==1 and n==0:
    return 1
  elif x==4*2**n-3:
    return 2*2**n-1
  elif x <= 4*2**(n-1)-3 +1:
    return func(n-1, x-1)
  else:
    return  func(n-1, 2*2**n-3) + func(n-1,x-2*2**n+1) +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 f(n, x):
  if n == 0:
    if x <= 0: return 0
    else:return 1
  elif x <= 1 + a[n-1]:
    return f(n-1,x-1)
  else:
    return p[n-1] + 1 + f(n-1, x-2-a[n-1])

print(f(n,x))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def a(n):
    return 2 ** (n + 2) - 3

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

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

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

Submission status: Accepted

Solution code:

m={}
def bits(n):
    if n in m:
        return m[n]
    elif n==0:
        m[n]=1
        return 1
    else:
        m[n]=((1+bits(n-1))*2+1)
        return m[n]
c={}
def pat(n):
    if n in c:
        return c[n]
    elif n==0:
        c[n]=1
        return c[n]
    else:
        c[n]=1+pat(n-1)*2
        return c[n]

def func(n, x):
    if n==0:
        return 1
    if x <=1:
        return 0
    elif x-1 <= bits(n-1):
        return func(n-1, x-1)
    elif x-1-bits(n-1)<=1:
        return pat(n-1)+1
    else:
        return pat(n-1)+1+func(n-1, x-1-bits(n-1)-1)

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

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

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

def get_x(n,x):
    if n == 0:
        return int(x>0)
    tmp_len = burger_len[n-1]
    if x <= (tmp_len +1):
        return get_x(n-1,x-1)
    elif x == tmp_len + 2:
        return 1 + burger_putty[n-1]
    else:
        return burger_putty[n-1] + 1 + get_x(n-1,x-tmp_len-2)

print(get_x(N,X))

Submission status: Accepted

Solution code:
# B-R()-P-R()-B

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

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

# layer k, rest x
def f(k, x):
    if x == 0:
        return 0
    if k == 0:
        assert x == 1
        return 1

    ret = 0

    # 一番左の B を食べる
    if x <= 1:
        return ret
    x -= 1

    # L-1 を食べる
    # 枚数は分かっている (total, psum) ので全部食べられるならそれを使って終わり
    # 切れ目が途中にある場合は再帰呼び出し
    if x <= total[k - 1]:
        return ret + f(k - 1, x)
    ret += psum[k - 1]
    x -= total[k - 1]

    # 真ん中の P を食べる
    if x < 1:
        return ret
    ret += 1
    x -= 1

    # 2回目の L-1 を食べる
    if x <= total[k - 1]:
        return ret + f(k - 1, x)
    ret += psum[k - 1]
    x -= total[k - 1]

    # 最後の B を食べる (残り 0 or 1 でないと何かがおかしい)
    assert x <= 1
    return ret

print(f(N, X))

Submission status: Accepted

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

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

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

print(Burger(N, X))

Submission status: Accepted

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

def f(N,X):
    if N == 0:
        return 1
    elif X == 1:
        return 0
    elif X <= 1 + bg_cnt[N-1]:
        return f(N-1,X-1)
    elif X == 2 + bg_cnt[N-1]:
        return 1 + f(N-1,X-1)
    else:
        return pan_cnt[N-1] + 1 + f(N-1,X-2-bg_cnt[N-1])    
print(f(N,X))

Submission status: Accepted

Solution code:
# /usr/bin/python
# -*- coding: utf-8 -*-
#
import sys
import math


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

cntr = [1]
keta = [1]

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

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    d, g = LI()
    pc = LIR(d)
    g = g // 100
    max_ = 0
    for i in range(d):
        pc[i][1] = pc[i][1] // 100
        max_ = max(pc[i][0], max_)
    dp = [float("INF") for i in range(g+1)]
    skip = [0 for i in range(max_+1)]
    if d >= g:
        print(1)
        return
    dp[0] = 1
    for i in range(d):
        skip[pc[i][0]] = max(skip[pc[i][0]], pc[i][1] + i + 1)
    x = 0
    for k in range(max_+1):
        if x <= skip[k]:
            for i in range(x + 1, skip[k] + 1):
                if i > g:
                    break
                dp[i] = k
            x = skip[k]
    for i in range(d + 1):
        dp[i] = 1
    i = d
    y = d
    while i < g:    
        for x in range(d):
            continue
        
        
     


    
    return

#D
def D():
    N, X = LI()
    def dfs(n, x):
        #print(n, x)
        if x == 1 and n > 0:
            return 0 
        elif x < 2 ** (n + 1) - 1:
            return dfs(n - 1, x - 1)
        elif x == 2 ** (n + 1) - 1:
            return 2 ** n 
        elif x == 2 ** (n + 2) - 3:
            return 2 ** (n + 1) - 1
        else:
            return dfs(n - 1, x - 2 ** (n + 1) + 1) + 2 ** n 
    a = dfs(N, X)
    print(a)
        
    return


#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
def rec(L, X):
    S = [0 for i in range(51)]
    S[0] = 1
    for i in range(1, 51):
        S[i] = 3 + 2 * S[i - 1]
    dic = {}
    def f(L, X):
        if L == 0:
            return 1
        if X < 2:
            return 0
        if (L, X) in dic:
            return dic[(L, X)]
        if X < S[L - 1] + 1:
            dic[(L, X)] = f(L - 1, X - 1)
        elif X == S[L - 1] + 1:
            dic[(L, X)] = f(L - 1, S[L - 1])
        elif X == S[L - 1] + 2:
            dic[(L, X)] = f(L - 1, S[L - 1]) + 1
        else:
            dic[(L, X)] = f(L - 1, S[L - 1]) + 1 + f(L - 1, X - 2 - S[L - 1])
        return dic[(L, X)]
    return f(L, X)

L, X = map(int, input().split())
print(rec(L, X))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    n,k = LI()
    h = IR(n)
    h.sort()
    ans = float("inf")
    for i in range(n-k+1):
        ans = min(ans,h[i+k-1]-h[i])
    print(ans)

#D
def D():
    n,x = LI()
    l = [1 for i in range(n+1)]
    for i in range(n):
        l[i+1] = 2*l[i]+3
    p = [1 for i in range(n+1)]
    for i in range(n):
        p[i+1] = 2*p[i]+1
    ans = 0
    for i in range(1,n+1)[::-1]:
        if i == 1:
            if x == 5:ans += 3
            else:ans += max(0,x-1)
        else:
            if x == 0:continue
            if x == l[i]:
                ans += p[i]
                x = 0
            if x > l[i-1]+1:
                ans += p[i-1]+1
                x -= l[i-1]+2
            else:
                x -= 1
    print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Accepted

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

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

#print(P)
#print(A)
 
def dfs(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    elif 1 < x <= 1 + A[n - 1]:
        return dfs(n - 1, x - 1)
    elif x == 1 + A[n - 1] + 1:
        return P[n - 1] + 1
    elif 1 + A[n - 1] + 1 < x < 1 + A[n - 1] + 1 + A[n - 1] + 1:
        return P[n - 1] + 1 + dfs(n - 1, x - 1 - A[n - 1] - 1)
    elif x >= 1 + A[n - 1] + 1 + A[n - 1] + 1:
        return P[n - 1] + 1 + P[n - 1]
    
print(dfs(n, x))

Submission status: Accepted

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

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

#print(P)
#print(A)
 
def dfs(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    elif x <= 1 + A[n - 1]:
        return dfs(n - 1, x - 1)
    elif x == 1 + A[n - 1] + 1:
        return P[n - 1] + 1
    elif 1 + A[n - 1] + 1 < x < 1 + A[n - 1] + 1 + A[n - 1] + 1:
        return P[n - 1] + 1 + dfs(n - 1, x - 1 - A[n - 1] - 1)
    elif x >= 1 + A[n - 1] + 1 + A[n - 1] + 1:
        return P[n - 1] + 1 + P[n - 1]
    
print(dfs(n, x))

Submission status: Accepted

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

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

#print(P)
#print(A)

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

print(dfs(n, x))

Submission status: Accepted

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

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

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

#print(P)
#print(A)

def dfs(n, x):
    cnt = 0
    if n == 0:
        return 1
    if x == 1:
        cnt += 0
    elif x <= 1 + A[n - 1]:
        cnt += dfs(n - 1, x - 1)
    elif x == 1 + A[n - 1] + 1:
        cnt += P[n - 1] + 1
    elif 1 + A[n - 1] + 1 < x < 1 + A[n - 1] + 1 + A[n - 1] + 1:
        cnt += P[n - 1] + 1 + dfs(n - 1, x - 1 - A[n - 1] - 1)
    elif x >= 1 + A[n - 1] + 1 + A[n - 1] + 1:
        cnt += P[n - 1] + 1 + P[n - 1]
    return cnt

print(dfs(n, x))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
h=[1]*(n+1)
p=[1]*(n+1)
for i in range(1, n+1):
    h[i]=3+h[i-1]*2
for i in range(1, n+1):
    p[i]=p[i-1]*2+1
def f(m, y):
    if m==0:
        return 1
    if y==1:
        return 0
    if y<=h[m-1]+1:
        return f(m-1, y-1)
    if y==h[m-1]+2:
        return p[m-1]+1
    if y<=h[m-1]*2+2:
        return f(m-1, y-h[m-1]-2)+p[m-1]+1
    if y==h[m-1]*2+3:
        return p[m-1]*2+1
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:
		return 0 if X <= 0 else 1
	elif 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]+3 <= X <= 2*a[N-1]+2:
		return f(N-1, X-2-a[N-1]) + p[N-1] + 1
	else:
		return p[N]

print(f(N, X))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
l=[2**(i+2)-3 for i in range(N+1)]#レベルLバーガー層数
p=[2**(i+1)-1 for i in range(N+1)]#レベルL パティ数
def f(n,x):
    if n==0:
        return 1
    elif x==1:
        return 0
    elif 1<x<=l[n-1]+1:
        return f(n-1,x-1)
    elif x==l[n-1]+2:
        return p[n-1]+1
    elif l[n-1]+2<x<l[n]:
        return p[n-1]+1+f(n-1,x-l[n-1]-2)
    elif x==l[n]:
        return p[n]
print(f(N,X))

Submission status: Accepted

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

p_num = []
pb_num = []
for i in range(n+1):
  if i == 0:
    p_num.append(1)
    pb_num.append(1)
  else:  
    p_num.append(p_num[-1] * 2 + 1)
    pb_num.append(pb_num[-1] * 2 + 3)
    
def get_p_num(n, x):
  if n == 0 and x == 1:
    return 1
  
  if x == 1:
    return 0
  elif x < (pb_num[n] + 1)//2:
    return get_p_num(n-1, x-1)
  elif x == (pb_num[n] + 1)//2:
    return p_num[n-1] + 1
  elif x < pb_num[n]:
    return p_num[n-1] + 1 + get_p_num(n-1, x - pb_num[n-1] - 2)
  else:
    return p_num[n-1] * 2 + 1
                 
print(get_p_num(n, x))

Submission status: Accepted

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

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

def patty(N,X):
	if N==1:
		l = [0,1,2,3,3]
		return l[X-1]
	elif N>=2:
		if X == 1:
			return 0
		elif X <= height[N-1]+1:
			return patty(N-1,X-1)
		elif X == height[N-1]+2:
			return patty(N-1,height[N-1])+1
		elif X == height[N]:
			return patty(N-1,height[N-1])*2+1
		elif X >= height[N-1]+3:
			return patty(N-1,height[N-1])+1+ patty(N-1,X-2-height[N-1])

print(patty(N,X))

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 <= 4*(2**(N-1))-2:
        return f(N-1,X-1)
    elif X == 4*(2**(N-1))-1:
        return 2**N
    elif X <= 4*2**N - 3:
        return 2**N + f(N-1,X - 4*(2**(N-1)) + 1)
    else:
        return 2**(N+1) - 1

print(f(n,x))

Submission status: Accepted

Solution code:
N, X = [int(x) for x in input().split()]
INF = 10**9

layer_num = [1]
p = [1]

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


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


print(rec(N, X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
result = [[]] * (N + 1)
result[0] = [1, 1] #[all-num, patty-num]
for i in range(1, N + 1):
    result[i] = [
        result[i - 1][0] * 2 + 3,
        result[i - 1][1] * 2 + 1,
    ]

def count_patty(idx, remain):
    if remain >= result[idx][0]:
        return result[idx][1]
    if remain <= 1:
        return 0
    ret = 0
    if remain >= result[idx][0] // 2 + 1:
        ret += result[idx - 1][1]
        ret += 1
        remain -= result[idx][0] // 2
    ret += count_patty(idx - 1, remain - 1)
    return ret

print(count_patty(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 burger(N, X):
    if N == 0:
        return 0 if X <= 0 else 1

    elif X <= 1 + a[N-1]:
        return burger(N-1, X-1)

    else:
        return p[N-1] + 1 + burger(N-1, X-2-a[N-1])

print(burger(N, X))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, X):
    @lru_cache(maxsize=None)
    def p(n):
        if n == 0:
            return 1
        return 2*p(n-1) + 1
    
    @lru_cache(maxsize=None)
    def a(n):
        if n == 0:
            return 1
        return 2*a(n-1) + 3
    
    def f(n, x):
        if x == 1:
            return 0
        
        elif x < a(n-1)+1:
            return f(n-1, x-1)
        
        elif x == a(n-1) + 1:
            return p(n-1)

        elif x == a(n-1) + 2:
            return p(n-1) + 1

        elif x < a(n) - 2:
            return p(n) - f(n-1, a(n)-x-1)
        
        else:
            return p(n)
    
    return f(N, X)

# BBPPPBPBPPPBB

def main():
    N, X = read_int_n()
    print(slv(N, X))

    # print(slv(2, 13))
    # # for i in range(1, 14):
    # #     print(i, slv(2, i))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:

def p(i: int) -> int:
    """レベルiバーガーのパティの数
    p[i] = 2*p[i-1] + 1
    p[i] + 1 = 2*(p[i-1] + 1)
    p[i] + 1 = (2**i)*(p[0] + 1)
    p[i] + 1 = (2**i)*2
    p[i] = 2**(i+1) - 1
    """
    return 2**(i+1) - 1


def a(i: int) -> int:
    """レベルiバーガーの層の数(パティとパンの数)
    a[i] = 2*a[i-1] + 3
    a[i] + 3 = 2 * (a[i-1] + 3)
    a[i] + 3 = (2**i) * (a[0] + 3)
    a[i] + 3 = (2**i) * 4
    a[i] = (2**(i+2)) - 3
    """
    return 2**(i+2) - 3


def f(N: int, X: int) -> int:
    """レベルNバーガーの下からX層の中に含まれるパティの数
    :param N: バーガーのレベル
    :param X: パティの数を調べたい層の数
    :return: パティの数
    """
    if N == 0:
        return 1 if X > 0 else 0

    an = a(N)
    if X < an // 2 + 1:
        # レベルN-1バーガーに含まれる。
        return f(N-1, X-1)
    if X == an // 2 + 1:
        # 中央のパティ + レベルN-1バーガーに含まれる全てのパティ
        return 1 + p(N-1)
    # レベルN-1バーガの全てのパティ + 中央のパティ
    # + レベルN-1バーガの下から(X-(ai+2))そうに含まれるパティ
    return 1 + p(N-1) + f(N-1, X-(an // 2 + 1))


if __name__ == "__main__":
    N, X = map(int, input().split())
    ans = f(N, X)
    print(ans)

Submission status: Accepted

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

b_num_arr = [1]
p_num_arr = [1]
for i in range(1, 51):
    b_num_arr.append(b_num_arr[-1]*2+3)
    p_num_arr.append(p_num_arr[-1]*2+1)


def burger_eat(n, x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    x -= 1
    if x < b_num_arr[n-1]:
        return burger_eat(n-1, x)
    pre_eat = p_num_arr[n-1]
    x -= b_num_arr[n-1]
    if x == 0:
        return pre_eat
    x -= 1
    pre_eat += 1
    return pre_eat + burger_eat(n-1, x)

ans = burger_eat(N, X)

print(ans)

Submission status: Accepted

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

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

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

print(f(N,X))

Submission status: Accepted

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

def rep(N,X):
    if N == 1:
        if X == 1:
            return(0)
        elif X == 5:
            return(3)
        else:
            return(X-1)
    elif X == 1:
        return(0)
    else:
        n = 2**(N+2)-3
        p = 2**N-1 # N-1のPの個数
        if X <= n//2:
            return(rep(N-1, X-1))
        elif X == n//2+1:
            return(p + 1)
        else:
            if n-1 == X-1:
                return(rep(N-1, X-1-n//2-1) + p + 1)
            else:
                return(rep(N-1, X-1-n//2) + p + 1)
print(rep(N,X))

Submission status: Accepted

Solution code:
N,K=map(int,input().split())
L=[1]
P=[1]
BG=[0]
for i in range(1,N+1):
  L.append(L[i-1]*2+3)
  P.append(P[i-1]*2+1)
def f(x,y):
  if x==0:
    if y==0:
      return 0
    if y==1:
      return 1
  elif y<=1:
    return 0
  elif 1<y<=L[x-1]+1:
    return f(x-1,y-1)
  elif L[x-1]+1<y<L[x]:
    return P[x-1]+1+f(x-1,y-2-L[x-1])
  elif y==L[x]:
    return P[x]
print(f(N,K))

Submission status: Accepted

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools


sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]


def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    global a, p
    N, X = LI()
    #  N = 50
    #  X = 4321098765432109
    a, p = [1], [1]
    for i in range(N):
        a.append(a[i] * 2 + 3)
        p.append(p[i] * 2 + 1)
    print(make_burger(N, X))
    return


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
ri = lambda: int(input())
rl = lambda: list(map(int,input().split()))

N,X=rl()

p = [0]*(N+1)
l = [0]*(N+1)
p[0]=1
l[0]=1

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


ans = 0

for i in range(N-1,-1,-1):
    if X==1:
        X -= 1
        break
    elif X <= 1+l[i]:
        X -= 1
        if i == 0:
            ans += 1
            break
    elif X == 1+l[i]+1:
        X -= 1+l[i]+1
        ans += p[i]+1
        break
    elif X <= 2+2*l[i]:
        X -= 2+l[i]
        ans += p[i]+1
        if i == 0:
            ans += 1
            break
    else:
        X -= 3+2*l[i]
        ans += 2*p[i]+1
        break
print(ans)

Submission status: Accepted

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

if x == 1:
    print(0)
    exit()

b = [0 for _ in range(n + 1)]
p = [0 for _ in range(n + 1)]

b[0] = 1
p[0] = 1

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

def burger(s, t):
    if t == 0:
        return 0
    if s == 0:
        return 1
    if t <= b[s - 1]:
        return burger(s - 1, t - 1)
    elif t == b[s - 1] + 1:
        return p[s - 1]
    elif t == b[s - 1] + 2:
        return p[s - 1] + 1
    else:
        return burger(s - 1, t - b[s - 1] - 2) + p[s - 1] + 1

print(burger(n, x))

Submission status: Accepted

Solution code:
bargarls = [0]*51;patyls = [0]*51
def bargar(n):
        global bargarls
        if n==1:
                bargarls[n-1] = 1
                return 1
        else:
                num = 2*bargar(n-1) + 3
                bargarls[n-1] = num
                return num
def paty(n):
        global patyls
        if n == 1:
                patyls[n-1] = 1
                return 1
        else:
                num = 2*paty(n-1) + 1
                patyls[n-1] = num
                return num
bargar(51)
paty(51)
def ans(n,x):
        global patyls 
        global bargarls
        if n >= x:return 0
        elif (bargarls[n]+1)//2 > x:return ans(n-1,x-1)
        elif (bargarls[n]+1)//2 == x:return (patyls[n]+1)//2
        elif bargarls[n] == x:return patyls[n]
        else:return (patyls[n]+1)//2 + ans(n-1,x-(bargarls[n]+1)//2)
n,x = map(int,input().split())
print(ans(n,x))

Submission status: Accepted

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

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

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

Submission status: Accepted

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


Patti = [1]  # レベルLバーガーに含まれているパティの数
Size = [1]   # レベルLバーガーの大きさ
for i in range(50):
    Patti.append(Patti[-1] * 2 + 1)
    Size.append(Size[-1] * 2 + 3)


def solve(n, x):
    # 一番下のバンのみ（ただしレベル0バーガーはPになる）
    if x == 1:
        return 0 + (n == 0)

    # 一番下のバン + レベルL-1バーガーのどこかまで
    if 1 < x <= 1 + Size[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティまで
    if x == 1 + Size[n - 1] + 1:
        return Patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    if 1 + Size[n - 1] + 1 < x < Size[n]:
        return 1 + Patti[n - 1] + solve(n - 1, x - (1 + Size[n - 1] + 1))

    # レベルLバーガーすべて
    if x == Size[n]:
        return Patti[n]


print(solve(N, X))