Problem:


Score : 400 points

Problem Statement

In some other world, today is Christmas.

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

A level-0 burger is a patty.

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

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

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

Constraints

1 \leq N \leq 50

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

N and X are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

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

Sample Input 1

2 7

Sample Output 1

4

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

Sample Input 2

1 1

Sample Output 2

0

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

Sample Input 3

50 4321098765432109

Sample Output 3

2160549382716056

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



Sample input:
2 7


Sample output:
4

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, x = [int(x) for x in input().strip().split()]
burgers = [False] * (n + 1)
burgers[0] = 'p'
leng = [1] * (n + 1)
patties = [1] * (n + 1)
for i in range(1, n+1):
    leng[i] = 2 * leng[i-1] + 3
    patties[i] = 2 * patties[i-1] + 1
def burger(l, x):
    if l == 0:
        ret = 1
    elif x == 1:
        ret = 0
    elif x <= leng[l] // 2:
        ret = burger(l-1, x-1)
    elif x == leng[l] // 2 + 1:
        ret = burger(l-1, x-2) + 1
    elif x < leng[l] - 2:
        ret = burger(l-1, leng[l-1]) + 1 + burger(l-1, x-2-leng[l-1])
    else:
        ret = patties[l]
    return ret

print(burger(n, x))

Submission status: Accepted

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


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


ans = f(n, x)
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, X = list(map(int, sys.stdin.buffer.readline().split()))

sizes = [1]
for _ in range(N):
    sizes.append(sizes[-1] * 2 + 3)
patties = [1]
for _ in range(N):
    patties.append(patties[-1] * 2 + 1)


def solve(n, x):
    if sizes[n] <= x:
        return patties[n]
    if x <= 0:
        return 0
    ret = 0
    ret += solve(n - 1, x - 1)
    ret += 1 if x > sizes[n] // 2 else 0
    ret += solve(n - 1, x - sizes[n] // 2 - 1)
    return ret


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

Submission status: Accepted

Solution code:
ri = lambda: map(int, input().split(' '))
L = [1]
C = [1]

def rec(n, x):
	if x == 0:
		return 0

	if n == 0:
		return 1

	if x == L[n]:
		return 2*C[n-1] + 1

	ans = 0
	if x >= L[n-1] + 2:
		ans += C[n-1] + 1
		ans += rec(n-1, x-L[n-1]-2)
	else:
		ans += rec(n-1, x-1)

	return ans

if __name__ == '__main__':
	N, X = ri()
	for i in range(1, N+1):
		L.append(2*L[i-1] + 3)
		C.append(2*C[i-1] + 1)
	ans = rec(N, X)
	print(ans)

Submission status: Accepted

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

dp = [0] * (N + 1)
p_dp = [0] * (N + 1)
dp[0] = 1
p_dp[0] = 1
for i in range(1, N + 1):
    dp[i] = dp[i - 1] * 2 + 3
    p_dp[i] = p_dp[i - 1] * 2 + 1
patties = p_dp[N]
burger_len = dp[N]

tmp = X
middle = -(-dp[N]//2)
n = N - 1
ans = 0
while True:
    #print("middle:", middle)
    #print("tmp:", tmp)
    if tmp == 1:
        if middle == 1:
            ans += 1
        break
    if tmp == middle:
        ans += p_dp[n] + 1
        break
    if tmp == dp[n + 1]:
        ans += p_dp[n] * 2 + 1
        break
    if 1 < tmp < middle:
        middle = -(-dp[n]//2)
        tmp -= 1
        n -= 1
    if middle < tmp < dp[n + 1]:
        tmp -= middle
        middle = -(-dp[n]//2)
        ans += p_dp[n] + 1
        n -= 1
print(ans)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
ans=0
def rec(x,n):
    global ans
    if n==0:
        if x>=1:
            ans+=1
    elif x>2**(n+1)-2:
        ans+=(2**n-1+1)
        rec(x-(2**(n+1)-1),n-1)
    else:
        rec(x-1,n-1)

rec(X,N)
print(ans)

Submission status: Accepted

Solution code:
def main():
    N, X = (int(i) for i in input().split())

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

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

    print(f(N, X))


if __name__ == '__main__':
    main()

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:
n,x = map(int,input().split())

a,p = [1],[1] #a:all,p:pate
for i in range(n):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)

def func(n,x): #n:バーガーの次元、x:下から何層か
    if n == 0: #終了条件：0次元まで逆算で戻る
        if x <= 0: #0次元の時、一応パテは1枚あるので、xが1余ってる場合を考慮
            return 0
        else:
            return 1
    elif x <= 1 + a[n-1]: #xがその次元の枚数より少ないなら
        return func(n-1,x-1)
    else:
        return p[n-1]+1+func(n-1,x-2-a[n-1])

print(func(n,x))

Submission status: Accepted

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

def paty(n,x):
  #print('n:{}'.format(n))
  #print('x:{}'.format(x))
  if x == 0:
    return 0
  if n == 0:
    return x
  elif ((2**(n+2))-3 - 1) / 2 >= x:
    return paty(n-1,x-1)
  elif ((2**(n+2))-3 + 1) / 2 == x:
    return 2**n
  elif ((2**(n+2))-3) - 1 <= x:
    return 2**(n+1) - 1
  else:
    return 2**n + paty(n-1, x-((2**(n+1))-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Accepted

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

# a[i]: レベルiの総数
a = [1]
# p[i]: レベルiのパティの総数
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 <= 1 + a[n-1]:
        return f(n-1,x-1)
    else:
        return p[n-1] + 1 + f(n-1,x-2-a[n-1])

print(f(N,X))

Submission status: Accepted

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

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

Submission status: Accepted

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

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


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


def solve():
    ans = calc(N, X)
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
S = 0
M = 2 ** (N + 2) - 3
P = 2 ** (N + 1) - 1
for i in range(N+1):
  P -= 1
  P //= 2
  M -= 1
  M //= 2
  if X - 1 == 0:
    if M != 0:
      break
    else:
      S += 1
      break
  if X - 1 == M:
    S += 1 + P
    break
  elif X - 1 == 2 * M:
    S += 1 + 2 * P
    break
  elif (X - 1) % M != 0 and (X - 1) > M:
    S += 1 + P
    X -= M + 1
    M -= 1
  elif (X - 1) % M != 0 and (X - 1) < M:
    X -= 1
    M -= 1
print(S)

Submission status: Accepted

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

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

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



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

print(f(N,X))

Submission status: Accepted

Solution code:
L, X=map(int, input().split())
def h(l):
  if l==0:
    return 1
  else:
    return h(l-1)*2+3

def f(l,x):
  if l == 0:
    if x == 0:
      return 0
    else:
      return 1
  else:
    if x <= 1:
      return 0
    elif x <= h(l-1) + 1:
      return f(l-1, x-1)
    elif x == h(l-1) + 2:
      return f(l-1, h(l-1))+1
    elif x <= h(l-1) * 2 + 2:
      return f(l-1, h(l-1))+1+f(l-1, x - h(l-1) - 2 )
    else:
      return f(l-1, h(l-1)) * 2 + 1
print(f(L,X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
A=[0]*51
B=[0]*51
A[0]=1
B[0]=1
i=1
while i<=50:
  A[i]=A[i-1]*2+3
  B[i]=B[i-1]*2+1
  i=i+1
#print(A)
#print(A[50])
#print(B[50])
ans=0
if n>=2:
  for i in range(n-1,0,-1):
    #print(i)
    if x==1 or x==0:
      break
    elif 1<x and x<=1+A[i]:
      x=x-1
    elif x==2+A[i]:
      ans=ans+B[i]+1
      break
    elif 2+A[i]<x and x<A[i+1]:
      ans=ans+B[i]+1
      x=x-A[i]-2
    else:
      ans=ans+2*B[i]+1
      break
    if i==1:
      if x==2:
        ans=ans+1
      elif x==3:
        ans=ans+2
      elif x==4 or x==5:
        ans=ans+3
  print(ans)
else:
  if x==1:
    print(0)
  elif x==2:
    print(1)
  elif x==3:
    print(2)
  elif x==4:
    print(3)
  elif x==5:
    print(3)

Submission status: Accepted

Solution code:
from functools import lru_cache
n,x=map(int,input().split())
h=[1]
for i in range(1,n):
    h.append(2*h[i-1]+3)
@lru_cache(None)
def run(l,x):
    if x==0:
        return 0
    if l==0:
        return 1
    else:
        if x<=h[l-1]+1:
            return run(l-1,x-1)
        elif x==h[l-1]+2:
            return run(l-1,h[l-1])+1
        else:
            return run(l - 1, h[l - 1]) + 1 \
                 + run(l - 1, x - h[l - 1] - 2)
print(run(n,x))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
#N=3
#M=7

MEMO=[[0]*(2) for i in range(N+1)]
MEMO[0][0]=1
MEMO[0][1]=1

for i in range (1,N+1):
    MEMO[i][0]=MEMO[i-1][0]*2+3
    MEMO[i][1]=MEMO[i-1][1]*2+1
t=1
s=0
n=N-1
f=0
while(True):
        if(t==M):break
        if(t+MEMO[n][0]<M):
            if f==0:
                t=t+MEMO[n][0]+1
                s+=MEMO[n][1]+1
                f+=1
            else:
                s+=MEMO[n][1]
                break
        elif(t+MEMO[n][0]>M):
            t+=1
            n-=1
            f=0
        else:
            s+=MEMO[n][1]
            break
print(s)

Submission status: Accepted

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

L = [2**(i+2) - 3 for i in range(51)] + [0]
P = [2**(i+1) - 1 for i in range(51)] + [0]

answer = 0
for i in range(N, -1, -1):
  if K == (L[i] + 1) // 2:
    answer += P[i-1] + 1
    break
  elif K > (L[i] + 1) // 2:
    answer += P[i-1] + 1
    K -= (L[i] + 1) // 2
  else:
    K -= 1
  if K == 0:
    break
print(answer)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
Thick=[]
P=[]
a=1
b=1
for i in range(N+1):
  Thick.append(a)
  P.append(b)
  a=a*2+3
  b=b*2+1
def dfs(l,x):
  if l==0:
    return 1
  
  if x==1:
    return 0
  elif x==Thick[l]//2:
    return P[l-1]
  elif x==Thick[l]//2+1:
    return P[l-1]+1
  elif x==Thick[l]:
    return P[l-1]*2+1
  else:
    if x<Thick[l]//2:
      return dfs(l-1,x-1)
    else:
      return P[l-1]+1+dfs(l-1,x-(Thick[l]//2+1))

print(dfs(N,X))

Submission status: Accepted

Solution code:
from sys import stdin

n,x = [int(x) for x in stdin.readline().rstrip().split()]
p = [1]
t = [1]
for i in range(1,n+1):
    p.append(p[i-1]*2+1)
    t.append(t[i-1]*2+3)

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

print(f(n,x))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

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
    # Xがバンズ1枚とL-1バーガー1個分以下なら、
    # バンズ1枚を除いて(X-1)、L-1バーガーで同じ探索をするのと変わらない
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    # Xがバンズ1枚とL-1バーガー1個分より大きければ、
    # L-1バーガー1個分に入っているパティ + 1パティ+ Xを-2(一番下のバンズと真ん中のパティ)-(L-1バーガー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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, X = MAP()

# 各レベルでの層とパティの総数を前計算
A = [0] * (N+1)
P = [0] * (N+1)
A[0] = P[0] = 1
for i in range(1, N+1):
    A[i] = A[i-1] * 2 + 3
    P[i] = P[i-1] * 2 + 1

def rec(n, x):
    if n == 0:
        # 最後の1つは食べる残数がまだ残ってれば食べる
        if x >= 1:
            return 1
        else:
            return 0
    else:
        # 食べる残数が真ん中のパティより手前
        if x <= A[n] // 2:
            # 左半分しか考えなくていい(xから左端バンズ分は引く)
            return rec(n-1, x-1)
        # 真ん中のパティ以降まで食べる
        else:
            # 左半分の総取り + 真ん中パティ + 右からいくつか(xから左半分と真ん中パティ分は引く)
            return P[n-1] + 1 + rec(n-1, x - (A[n] // 2 + 1))
print(rec(N, X))

Submission status: Accepted

Solution code:
from bisect import bisect

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

P_N = [1]
L_N = [1]

for i in range(n):
  P_N.append(2*P_N[i]+1)
  L_N.append(2*L_N[i]+3)
  
def rec_check(n, x):
  if n==0:
    return(0 if x<=0 else 1)
  
  if x <= L_N[n-1]+1:
    return(rec_check(n-1, x-1))
  else:
    return(P_N[n-1]+1+rec_check(n-1, x-2-L_N[n-1]))
  
print(rec_check(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 solve(n,x): #n,x
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<=1+a[n-1]:
        return  solve(n-1,x-1)
    else:
        return p[n-1]+1+solve(n-1,x-2-a[n-1])

print(solve(N,X))

Submission status: Accepted

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

Submission status: Accepted

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

def num_patty(n, x):
  if 2**(n+2)-3 <= x:
    return 2**(n+1)-1
  elif 2**(n+1) <= x and x <= 2**(n+2)-4:
    return num_patty(n-1, x-2**(n+1)+1)+(2**n-1)+1
  elif x == 2**(n+1)-1:
    return (2**n-1)+1
  elif 2 <= x and x <= 2**(n+1):
    return num_patty(n-1, x-1)
  else:
    return 0
    
print(num_patty(n, x))

Submission status: Accepted

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

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

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

print(f(N, X))

Submission status: Accepted

Solution code:
import sys
def thk(n):
    return 2**(n+2)-3
def pt(n):
    return 2**(n+1)-1
def ban(n):
    return 2**(n+1)-2

N,X = map(int, input().split(' '))
ans = 0

while(True):
    if X == 0:
        break
    elif X == thk(N)//2+1:
        ans += pt(N-1)+1
        break
    elif X == thk(N):
        ans += 2*pt(N-1)+1
        break
    elif X > thk(N)//2+1:
        ans += pt(N-1)+1
        X -= thk(N)//2+1
        N -= 1
    else:
        X -= 1
        N -= 1

print(ans)

Submission status: Accepted

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

# 層の総数
T = [1]
for i in range(1, 50+1):
    T.append(T[i-1]*2+3)

def hash(n,x):
    return "{0:d},{1:d}".format(n,x)

# レベルnバーガーの下からx層内のパティの数
memo = dict()
def solve(n,x):
    global T, memo
    if hash(n,x) in memo:
        return memo[hash(n,x)]
    if n == 0 and x >= 1:
        memo[hash(n,x)] = 1
        return 1
    if x <= 1:
        memo[hash(n,x)] = 0
        return 0
    memo[hash(n,x)] = solve(n-1, min(x-1, T[n-1]))
    if x >= T[n-1]+2:
        memo[hash(n,x)] += 1
    if x >= T[n-1]+3:
        memo[hash(n,x)] += solve(n-1, min(x-1-T[n-1]-1, T[n-1]))
    return memo[hash(n,x)]

print(solve(N,X))

Submission status: Accepted

Solution code:
def L(N, X):
    if N == 0:
        return 1

    a = 2 ** (N + 1) - 3
    b = 2 ** N - 1
    if X == 1:
        return 0
    elif X <= a + 1:
        return L(N-1, X-1)
    elif X == a + 2:
        return b + 1
    elif X <= 2 * a + 2:
        return b + 1 + L(N-1, X-a-2)
    else:
        return b * 2 + 1

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

print(num(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)
# print(A,P)

def func(n,x):
	if x == 1:
		return 0 if n != 0 else 1
	elif x <= 1+A[n-1]:
		return func(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+func(n-1,x-2-A[n-1])
	else:
		return 2*P[n-1]+1

print(func(n,x))

Submission status: Accepted

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


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

Submission status: Accepted

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

for i in range(100):
    if N == 0:
        count += 1
        break
    elif X == 1:
        break
    elif X == 2**(N+1) - 1:
        count += 2**N
        break
    elif X == 2**(N+2) - 3:
        count += 2**(N+1) - 1
        break
    elif 1 < X < 2**(N+1) - 1:
        X -= 1
        N -= 1
    elif 2**(N+1) - 1 < X < 2**(N+2) - 3:
        count += 2**N
        X -= 2**(N+1) - 1
        N -= 1

print(count)

Submission status: Accepted

Solution code:
import sys
n, x = [int(i) for i in sys.stdin.readline().split()]
cur = 1
p = 1
ls = [cur]
p_ls = [p]
for i in range(50):
    cur = cur * 2 + 3
    p = p * 2 + 1
    ls.append(cur)
    p_ls.append(p)

def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    if x == 1:
        return 0
    elif x <= 1 + ls[n-1]:
        return f(n-1, x-1)
    elif x == ls[n-1] + 2:
        return 1 + p_ls[n-1]
    elif x < ls[n]:
        return 1 + p_ls[n-1] + f(n-1, x - ls[n-1] - 2)
    else:
        return p_ls[n]
res = f(n, x)
print(res)

Submission status: Accepted

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

print(f(n,x))

Submission status: Accepted

Solution code:
#設定
import sys
input = sys.stdin.buffer.readline

#ライブラリインポート
from collections import defaultdict

#入力受け取り
def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, X = getlist()
	B = [0] * 51
	P = [0] * 51
	Size = [0] * 51
	P[0] = 1
	for i in range(50):
		B[i + 1] = 2 * B[i] + 2
		P[i + 1] = 2 * P[i] + 1
	for i in range(51):
		Size[i] = B[i] + P[i]

	def solve(N, X):
		if N == 0:
			return 1
		elif X == 1:
			return 0
		elif X <= 1 + Size[N - 1]:
			return solve(N - 1, X - 1)
		elif X == 2 + Size[N - 1]:
			return P[N - 1] + 1
		elif 2 + Size[N - 1] < X and X <= 2 + 2 * Size[N - 1]:
			return (P[N - 1] + 1 + solve(N - 1, X - 2 - Size[N - 1]))
		else:
			return 2 * P[N - 1] + 1

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

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    pre_P = [1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247 ]
    pre_total = [1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645, 4294967293, 8589934589, 17179869181, 34359738365, 68719476733, 137438953469, 274877906941, 549755813885, 1099511627773, 2199023255549, 4398046511101, 8796093022205, 17592186044413, 35184372088829, 70368744177661, 140737488355325, 281474976710653, 562949953421309, 1125899906842621, 2251799813685245, 4503599627370493]
    
    n,x=inpm()
    ans=0
    for i in range(n,0,-1):
        if x>=pre_total[i]-1:
            ans+=pre_P[i]
            break
        if x>=pre_total[i-1]+2:
            x-=pre_total[i-1]+2
            ans+=pre_P[i-1]+1
        elif x==pre_total[i-1]+1:
            ans+=pre_P[i-1]
            break
        else:
            x-=1
    print(ans)
        
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#レベルNのバーガーには2**(N+1)-1枚のパティ、2**(N+1)-2枚のバン

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

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

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
ans = 0
while X != 1 and X != 2**(N+1)-1 and X != 2**(N+2)-3:
    if 1 < X < 2**(N+1)-1:
        X -= 1
        N -= 1
    else:
        ans += 2**N
        X -= 2**(N+1)-1
        N -= 1
if X == 2**(N+1)-1:
    ans += 2**N
elif X == 1:
    ans += 0
else:
    ans += 2**(N+1)-1
print(ans)

Submission status: Accepted

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

from functools import lru_cache
import sys

sys.setrecursionlimit(10*20)

@lru_cache(maxsize=None)
def count(N):
    if N == 0:
        return 1
    else:
        return 3 + 2 * count(N-1)
    
@lru_cache(maxsize=None)
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))

Submission status: Accepted

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

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

print(counter(N,X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
burger_size = 1
patty_size = [1]
for _ in range(N):
    burger_size = burger_size*2+3
    patty_size.append(patty_size[-1]*2+1)
i = -2
ans = 0
left = 1
right = burger_size
for i in range(N, -1, -1):
    m = (left+right)//2
    if i == 0:
        ans += 1
        break
    elif left == X:
        break
    elif right == X:
        ans += patty_size[i-1]*2+1
        break
    elif m == X:
        ans += patty_size[i-1]+1
        break
    elif left < X < m:
        left += 1
        right = m-1
    else:
        ans += patty_size[i-1]+1
        left = m+1
        right -= 1

print(ans)

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:
#!/usr/bin/env python3
import sys

def solve(N: int, X: int):
    # amount[i] = level iバーガーのP+Bの総数
    amount = [0]*N
    amount[0] = 5
    for i in range(N-1):
        amount[i+1] = amount[i]*2 + 3

    # amount[i] = level iバーガーのPの総数
    p_amount = [0]*N
    p_amount[0] = 3

    for i in range(N-1):
        p_amount[i+1] = p_amount[i]*2 + 1
    
    # レベルNバーガーの下からX個に含まれるPの個数を返す
    def dfs(n,x) -> int:
        if x == 0:
            return 0
            
        if n == 1:
            if x == 1 or x == 0:
                return 0
            elif 2<= x <= 4:
                return x-1
            else:
                return 3


        half = (amount[n-1]-3)//2 + 1
        if x <= half:
            return dfs(n-1,x-1)
        else:
            res = x-half-1
            return p_amount[n-2]+1+dfs(n-1,res)
    
    print(dfs(N,X))
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def getItems(layerCount):
	if layerCount == 0:
		return 1
	return 2*getItems(layerCount-1) + 3

def getPats(layerCount):
	return 2**(layerCount + 1) - 1

def patEaten(layer, toEat):
	pattyCount = 0

	if layer == 1:
		burger = "BPPPB"

		for x in range(toEat):
			if burger[x] == "P":
				pattyCount += 1
		return pattyCount
		
	elif layer == 0:
		if toEat == 1:
			return 1
		else:
			return 0
	
	else:
		items = getItems(layer)
		if toEat == items:
			pattyCount += getPats(layer)
			return pattyCount
		elif toEat < 2+getItems(layer-1):
			if items + 1 == 2* toEat:
				toEat-=2
				return 1 + patEaten(layer - 1, toEat)
			toEat -= 1
			return patEaten(layer - 1, toEat)
		else:
			toEat -= (1+1+getItems(layer-1))
			pattyCount += 1 + getPats(layer-1)
			
			return pattyCount + patEaten(layer-1, toEat)

i, j = [int(x) for x in input().split()]
#print(patEaten(2,13))
print(patEaten(i,j))

Submission status: Accepted

Solution code:

a = None
p = None


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


def main():
    N, X = list(map(int, input().split()))
    global a
    global p
    a = [1]
    p = [1]

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

    print(f(N, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

L = [1] * (N+1)
p = [1] * (N+1)

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

print(search(X, N))

Submission status: Accepted

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


def solve(N, X):
    ret = 0
    if X == p[N]:
        return((p[N]+1) // 2)
    elif X <= N:
        return(0)
    else:
        if X >= (p[N] + 1) // 2:
            ret += ((p[N-1]+1) // 2) + 1
            X = X - (p[N-1] + 1)
        ret += solve(N-1, X-1)
        return(ret)


print(solve(N, X))