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

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

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 n == 0 and x > 0:
        ans += 1
        x -= 1
    elif 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)

Submission status: Accepted

Solution code:
A=[1]*51
for i in range(1,51):
    A[i]=2*A[i-1]+3

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

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

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
a=[1]
p=[1]
for i in range(1,N+1):
    a.append(a[i-1]*2+3)
    p.append(p[i-1]*2+1)
    
def f(n,x):#レベルnのハンバーガーをx段食べる
    if n ==0:#0段目の終了条件
        return 0 if x <=0 else 1

    if 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 cin():
    in_ = list(map(int,input().split()))
    if len(in_) == 1:  return in_[0]
    else:  return in_

N, X = cin()
a = [0 for _ in range(N)] # 全体の枚数
p = [0 for _ in range(N)] # パティの枚数
a[0] = 1
p[0] = 1

for i in range(1, N):
    a[i] = 2 * a[i - 1] + 3
    p[i] = 2 * p[i - 1] + 1
    
def f(N, X):
    if N == 0:  
        if X <= 0: return 0
        else:  return 1
    if X <= 1 + a[N - 1]:  return f(N - 1, X - 1)
    return 1 + p[N - 1] + f(N - 1, X - 2 - a[N - 1])

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

Submission status: Accepted

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

sumx=[1]
pathi=[1]
for i in range(n):
  sumx+=[sumx[-1]*2+3]
  pathi+=[pathi[-1]*2+1]
  
if n==0:
  if x==1:
    print(1)
    exit()
    
elif x==1:
  print(0)
  exit()
  

elif x==sumx[-1] or x==sumx[-1]-1:
  print(pathi[-1])
  exit()
  
ans=0

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


ans+=max(x-1,0)
print(ans)

Submission status: Accepted

Solution code:

        
def main():
    import sys

    def input(): return sys.stdin.readline().rstrip()

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

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





                
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
import numpy as np
import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

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 = [2 ** (i + 2) - 3 for i in range(n)]
burger2 = [2 ** (i + 1) - 1 for i in range(n)]
num = [0 for i in range(n)]
ans = 0
temp = n - 1
while x > 0:
    if x >= 1:
        x -= 1
    else:
        continue
    if x >= burger[temp]:
        num[temp] += 1
        x -= burger[temp]
    else:
        temp -= 1
        continue
    if x >= 1:
        ans += 1
        x -= 1
    else:
        continue
    if x >= burger[temp]:
        num[temp] += 1
        x -= burger[temp]
    else:
        temp -= 1
        continue
    if x >= 1:
        x -= 1
    else:
        continue
for i in range(n):
    ans += burger2[i] * num[i]
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
# a=レベルiバーガーの厚さ, p = レベルiバーガーのパティの数
a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

# レベルNバーガーの下からX層にあるパティの数


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

print(f(N, X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l,p=[1],[1]
for i in range(n):
  l+=[l[-1]*2+3]
  p+=[p[-1]*2+1]
x-=1
a=1
while n:
  t=l[n]//2
  if x>=t:
    a+=p[n-1]+1
    x-=t
  x-=1
  n-=1
if x<0: a-=1
print(a)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l,p=[1],[1]
for i in range(n):
  l+=[l[-1]*2+3]
  p+=[p[-1]*2+1]
x-=1
a=0
while x>0 and n:
  t=l[n]//2
  if x>=t:
    a+=p[n-1]+1
    x-=t
  x-=1
  n-=1
if x>=0 and n==0: a+=1
print(a)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, X = LI()
    X -= 1

    # バーガーの厚さ
    l = [0] * (N + 1)
    l[0] = 1
    for i in range(N):
        l[i+1] = 2 * l[i] + 3

    # バーガーのパティ数
    p = [0] * (N + 1)
    p[0] = 1
    for i in range(N):
        p[i+1] = 2 * p[i] + 1

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

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

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

def pNumber(level, number):
    if level == 0:
        return 1
    if number == 1:
        return 0
    if number <= burgerLengthList[level][0] // 2:
        return pNumber(level - 1, number - 1)
    elif number == burgerLengthList[level][0] // 2 + 1:
        return pNumber(level - 1, number - 1) + 1
    else:
        return burgerLengthList[level - 1][1] + 1 + pNumber(level - 1, number - burgerLengthList[level - 1][0] - 2)

print(pNumber(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 n_pati(l):
  val = 1
  for i in range(l):
    val = val*2+1
  return val

def n_layer(l):
  val = 1
  for i in range(l):
    val = val*2+3
  return val

SUM=0
while 1:
  if N==1:
    if X in [0,1]:break
    elif X>=2:
      SUM += min(3,X-1)
      break
  
  L = n_layer(N)
  if X >= L//2:
    SUM += n_pati(N-1)
    X -= n_layer(N-1)+1
    if X==0:
      break
    SUM += 1
    X -= 1
    if X==0:
      break
    N -= 1
  else:
    X -= 1
    N -= 1
    
  if X in [0,1]:break
  
print(SUM)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, X = mapint()
burger = [1]*50
pa = [1]*50
for i in range(1, 50):
    burger[i] = burger[i-1]*2+3
    pa[i] = pa[i-1]*2+1

to_eat = X
layer = N
ans = 0
while 1:
    if layer==0:
        ans += to_eat
        break
    if to_eat<=1:
        break
    elif to_eat==burger[layer-1]+2:
        ans += pa[layer-1]+1
        break
    elif to_eat==burger[layer-1]+1:
        ans += pa[layer-1]
        break
    elif to_eat==burger[layer-1]*2+3:
        ans += pa[layer-1]*2+1
        break
    elif to_eat<=burger[layer-1]:
        layer -= 1
        to_eat -= 1
        continue
    else:
        ans += pa[layer-1]+1
        to_eat -= burger[layer-1]+2
        layer -= 1

print(ans)

Submission status: Accepted

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

def rec(n,x):
    if n==0:
        ret = int(x>0)
    elif x <= 1 + siz[n-1]:
        ret = rec(n-1, x-1)
    else:
        ret = pat[n-1] + 1 + rec(n-1, x-2-siz[n-1])
    return ret
print(rec(N,X))

Submission status: Accepted

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

Total = [1]
Patties = [1]

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

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

print(Burger(N,X))

Submission status: Accepted

Solution code:
memo1 = {}
def cho(n):
    if n==0:
        return 1
    if n in memo1:
        return memo1[n]
    memo1[n] = 2*cho(n-1)+3
    return memo1[n]
memo2 = {}
def pat(n):
    if n==0:
        return 1
    if n in memo2:
        return memo2[n]
    memo2[n] = 2*pat(n-1)+1
    return memo2[n]
N,X = map(int,input().split())
cnt = 0
k = N
while X>0:
    if X==1:
        if k==0:
            cnt += 1
        break
    elif X<=cho(k)//2:
        k -= 1
        X -= 1
    elif X==cho(k)//2+1:
        cnt += 1+pat(k-1)
        break
    elif X==cho(k):
        cnt += pat(k)
        break
    else:
        cnt += pat(k-1)+1
        X -= cho(k-1)+2
        k -= 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

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

store = [pow(2,i+1)-1 for i in range(51)]

def maisu(n):
  return pow(2,n+2)-3

def burger(n,k): #n層でk枚
  if k == maisu(n):
    return store[n]
  elif k <= 1:
    return 0
  elif (maisu(n)-3)//2 +1 >= k:
    return burger(n-1,k-1)
  else:
    #print(k-(2+maisu(n-1)),maisu(n-1))
    return burger(n-1,k-(2+maisu(n-1)))+burger(n-1,maisu(n-1))+1
  
ans = burger(N,K)    
print(ans)

Submission status: Accepted

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

burger_size = [1]
patty_num = [1]
for i in range(50):
    burger_size.append(2 * burger_size[-1] + 3)
    patty_num.append(2 * patty_num[-1] + 1)


# レベルnバーガーの下からx段目までに含まれるパティの数を返す
def dfs(n, x):
    if burger_size[n] == x:
        return patty_num[n]

    if x == 1:
        return 0

    elif 1 < x <= 1 + burger_size[n - 1]:
        return dfs(n - 1, x - 1)

    elif x == 1 + burger_size[n - 1] + 1:
        return patty_num[n - 1] + 1

    elif 1 + burger_size[n - 1] + 1 < x < burger_size[n]:
        return patty_num[n - 1] + 1 + dfs(n - 1, x - burger_size[n - 1] - 2)


print(dfs(N, X))

Submission status: Accepted

Solution code:
n,x=map(int, input().split())
p=[1]*(n+1) #パティ
a=[1]*(n+1) #パティとバンズ

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

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

print(f(n,x))

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


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

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

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

    print(rec(N, X))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f(n, x, a, p):
    if n == 0:
        return 1 if x == 1 else 0

    elif x <= 1:
        return 0

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

    elif x == 2 + a[n - 1]:
        return p[n - 1] + 1

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

    else:
        return 1 + 2 * p[n - 1]


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

a = [1] * (n + 1)
p = [1] * (n + 1)

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

print(f(n, x, a, p))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
ans = 0
i = n
while i >= 0:
    c = 2**(i+1) - 3
    num_p = 2**i - 1
    
    if 2*c + 3 == x:
        ans += 2*num_p + 1
        break
    elif c + 2 == x:
        ans += num_p + 1
        break
    elif 1 == x:
        break
    
    elif 2 + c <= x:
        x -= 2 + c
        ans += num_p + 1
    else:
        x -= 1
    
    i -= 1

print(ans)

Submission status: Accepted

Solution code:
# 初期入力
import sys
input = sys.stdin.readline
N,X = (int(i) for i in input().split())
DP_all  =[0]*(N+1)
DP_p    =[0]*(N+1)
DP_all[0]   =1
DP_p[0]     =1

#レベル「i+1」バーガーの枚数
for i in range(N):
    DP_all[i+1] =DP_all[i] *2 +3
    DP_p[i+1]   =DP_p[i] *2  +1
#print("総枚数" ,DP_all)
#print("パティ枚数" ,DP_p)

#再帰でパティの枚数を求める L=レベル、x=食べる枚数
def  p_num(L,x):
    if x <=L:
        return 0
    if x ==DP_all[L]:
        return DP_p[L]
    elif x < DP_all[L] //2 +1:
        return p_num(L-1,x -1)
    elif x ==DP_all[L] //2 +1:
        return DP_p[L-1] +1
    elif x > DP_all[L] //2 +1:
        return DP_p[L-1] +1 +p_num(L-1,x -DP_all[L-1] -2)

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

Submission status: Accepted

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

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

print(rec(n, x))

Submission status: Accepted

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

ans = 0
while n >= 0:
    n -= 1
    if x == 0:
        # 左端
        if n == -1:
            ans += 1
        break
    elif 1 <= x <= lbl[n]:
        # 左側
        x -= 1
    elif lbl[n]+1 == x:
        # 真中
        ans += npl[n] + 1
        break
    elif lbl[n]+1 < x < 2*lbl[n]+2:
        # 右側
        x -= lbl[n]+2
        ans += npl[n]+1
    elif x == 2 + 2*lbl[n]:
        # 右端
        ans += 2*npl[n] + 1

print(ans)

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

ans = 0
for i in range(N, -1, -1):
    if i == 0 and X >= 1:
        ans += 1
        break

    if X <= 1:
        break
    elif X <= l[i - 1] + 1:
        X -= 1
        continue 
    elif X == l[i - 1] + 2:
        ans += 1
        X -= 2
    else:
        ans += p[i - 1] + 1
        X -= l[i - 1] + 2
print(ans)

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
ans=0
f=0
for i in range(N,1,-1):
    center = 2*pow(2,i)-1
    
    if X>center:
        X-=center
        ans+=pow(2,i)
    elif X==center:
        ans+=pow(2,i)
        f=1
        break
    elif X<center:
        X-=1

if f==0:
    ans+="BQQQB"[:X].count("Q")
print(ans)

Submission status: Accepted

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

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

lst = [1]

for _ in range(1,N+1):
  lst.append(2*lst[-1]+1)

pw = 2**(N+1)-3
rlt = 0
i = N-1
while 1:
  if X == 1:
    print(rlt)
    exit()
  elif X < pw+2:
    X -= 1
    pw = (pw-3)//2
    if i > 0: 
      i -= 1
    elif i == 0:
      print(rlt+1)
      exit()
  elif X == pw+2:
    rlt += lst[i]+1
    print(rlt)
    exit()
  elif X < 2*pw+3:
    X -= pw + 2
    pw = (pw-3)//2
    if i > 0:
      rlt += lst[i]+1
      i -= 1
    elif i == 0:
      print(rlt+3)
      exit()
  elif X == 2*pw+3:
    rlt += 2*lst[i]+1
    print(rlt)
    exit()

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
patty=[1]
barger=[1]
ans=0
for i in range(n):
  patty.append(2*patty[-1]+1)
  barger.append(2*barger[-1]+3)
i=n
while x>0:
  for _ in range(n):
    if x>=barger[i]:
      x-=barger[i]
      ans+=patty[i]
      if x>0:
        ans+=1
        x-=1
      break
    i-=1
    x-=1
print(ans)

Submission status: Accepted

Solution code:
# DFS用の関数.
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())
# n=0のとき、a,pを初期化.
a, p = [1], [1]
# 1<=n<=nのときの、a,pを逐次的に求める.
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(' '))

level2p = [1] * (N + 1)
level2pb = [1] * (N + 1)

for i in range(N):
    level2p[i + 1] = level2p[i] * 2 + 1
    level2pb[i + 1] = level2pb[i] * 2 + 3


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

    if x <= 1:
        return 0
    elif x <= 1 + level2pb[n - 1]:
        return dfs(n - 1, x - 1)
    elif x <= 1 + level2pb[n - 1] + 1:
        return level2p[n - 1] + 1
    elif x <= 1 + level2pb[n - 1] + 1 + level2pb[n - 1]:
        return level2p[n - 1] + 1 + dfs(n - 1, x - 1 - level2pb[n - 1] - 1)
    else:
        return level2p[n]


print(dfs(N, X))

Submission status: Accepted

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

p = [1]
pb = [1]
np = 0
nx = X

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


def dfs(level):
    global np, nx

    if nx == 0:
        return

    if nx >= pb[level]:
        nx -= pb[level]
        np += p[level]
        return

    nx -= 1
    if nx == 0:
        return

    dfs(level - 1)

    if nx == 0:
        return

    nx -= 1
    np += 1

    if nx == 0:
        return

    dfs(level - 1)

    if nx == 0:
        return

    nx -= 1


dfs(N)

print(np)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections
from decimal import Decimal # 10進数で考慮できる

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N, X = LI()

"""
Lv i のバーガーの厚みをa[i]
Lv i に含まれるパティの数をp[i]
とすると
a[0] = 1
a[i] = 2 * a[i-1] + 3
p[0] = 1
p[i] = 2 * p[i - 1] + 1

X = 1 f(N, X) = 0

1 < X <= 1 + a[i - 1]
一番したのバン

2 + a[i - 1] < X
一番したのバン　＋　
"""
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())
tp=0
for i in range(n):
    ct = (2**(n-i+2)-4)//2+1
    if x==0:break
    if i==n-1:tp+='bpppb'[:x].count('p')
    else:
        pn = 2**(n-i)-1
        if x<ct:x-=1
        elif x>=ct:
            tp+=pn+1
            if x==ct:break
            x-=ct
print(tp)

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:
def solve():
    n, x = map(int, input().split())
    l = [1]
    nu = [1]
    for i in range(n):
        l.append(l[-1] * 2 + 3)
        nu.append(nu[-1] * 2 + 1)

    def chris(a, b):
        if a == 0:
            return b
        elif b <= a:
            return 0
        hl = l[a]
        if b >= hl - a:
            return nu[a]
        elif hl // 2 + 1 <= b:
            return nu[a - 1] + 1 + chris(a - 1, b - (hl // 2 + 1))
        return chris(a - 1, b - 1)

    print(chris(n, x))


solve()

Submission status: Accepted

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

lev = N
cur = X-1
ps = 0
for i in range(N+1):
    if lev == 0:
        ps += 1
        break

    if cur == 0:
        break
    elif cur == sum(burger[lev-1])+1:
        ps += burger[lev-1][0]+1
        break
    elif cur == sum(burger[lev])-1:
        ps += 2*burger[lev-1][0] + 1
        break

    if cur < sum(burger[lev])/2:
        cur -= 1
        lev -= 1
    else:
        ps += burger[lev-1][0] + 1
        cur -= sum(burger[lev-1]) + 2
        lev -= 1
print(ps)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, X = mi()
    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

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X = MAP()

L = [0]*(N+1) #レベルiにおける全体の枚数
L[0] = 1

P = [0]*(N+1) #レベルiにおけるパティの枚数
P[0] = 1

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

def solve(i, x):  #レベルiの下からX層におけるパティの枚数
	if i == 0:
		if 0 < x:
			return 1
		else:
			return 0

	if x-1 <= L[i-1]:
		return solve(i-1, x-1)
	else:
		return P[i-1] + 1 + solve(i-1, x-L[i-1]-2)

print(solve(N, X))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X = MAP()

L = [0]*(N+1) #レベルiにおける全体の枚数
L[0] = 1

P = [0]*(N+1) #レベルiにおけるパティの枚数
P[0] = 1

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

def solve(i, x):  #レベルiの下からX層におけるパティの枚数
	if i == 0:
		if x <= 0:
			return 0
		else:
			return 1

	if x-1 <= L[i-1]:
		return solve(i-1, x-1)
	else:
		return P[i-1] + 1 + solve(i-1, x-L[i-1]-2)

print(solve(N, X))

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X = MAP()

L = [0]*(N+1) #レベルiバーガーの全体の層数
L[0] = 1
for i in range(1, N+1):
	L[i] = 2*L[i-1] + 3

P = [0]*(N+1) #レベルiバーガーのパティの数
P[0] = 1
for i in range(1, N+1):
	P[i] = 2*P[i-1] + 1

def solve(i, x): #レベルiバーガーの下からx個
	if i == 0:
		if x <= 0:
			return 0
		else:
			return 1
	if x <= L[i-1] + 1:
		ret = solve(i-1, x-1)
	else:
		ret = P[i-1] + 1 + solve(i-1, x - L[i-1] - 2)
	return ret


print(solve(N, X))

Submission status: Accepted

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

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


    def f(i,y):
        if i == 0:
            return 1
        if y == 1:
            return 0
        if 1 < y <= 1 + a[i-1]:
            return f(i-1,y-1)
        if y == 2 + a[i-1]:
            return p[i-1] + 1
        if 2 + a[i-1] < y <= 2 + a[i-1]*2:
            return p[i-1] + 1 + f(i-1,y-(2+a[i-1]))
        else:
            return p[i-1] * 2 + 1

    print(f(N,X))

    



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def S(): return sys.stdin.readline().rstrip()

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

def f(A,B):  # レベルAバーガーの下からB層に何枚パティがあるか
    if A == 0 and B == 1:
        res = 1
    else:
        if B == 1:
            res = 0
        elif 2 <= B <= 2**(A+1)-2:
            res = f(A-1,B-1)
        elif B == 2**(A+1)-1:
            res = 2**A
        elif 2**(A+1) <= B <= 2**(A+2)-2:
            res = 2**A + f(A-1,B-2**(A+1)+1)
        else:
            res = 2**(A+1)-1
    return res

print(f(N,X))