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: Time Limit Exceeded

Solution code:
def cnt(n, x):
	if x==0:
		return 0
	elif n==0:
		return 1
	elif x<2**(n+1)-1:
		return cnt(n-1, x-1)
	elif 2**(n+1)-1<=x and x<2**(n+2)-3:
		return cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1)+1)
	else:
		return cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1))

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

Submission status: Time Limit Exceeded

Solution code:

runrun_patty = 0
runrun_walk = 0
x = 0

def main():
    global x
    N, x = (int(i) for i in input().split())
    runrun(N)
    print(runrun_patty)


def runrun(l):
    global runrun_patty, runrun_walk, x
    if runrun_walk >= x:
        return

    if l == 0:
        runrun_patty = runrun_patty + 1  # パティ
        runrun_walk = runrun_walk + 1
        return
        
    runrun_walk = runrun_walk + 1   # パン

    runrun(l-1)                       # バーガー
    # runrun_walk = runrun_walk + 1
    
    if runrun_walk >= x:
        return
    runrun_patty = runrun_patty + 1  # パティ
    runrun_walk = runrun_walk + 1

    runrun(l-1)                       # バーガー
    # runrun_walk = runrun_walk + 1

    runrun_walk = runrun_walk + 1   # パン

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
@lru_cache(maxsize=3000)
def burger(str_b,level):
  if(level == 0):
    return str_b + 'p'
  str_b += 'B'
  str_b = burger(str_b,level-1)
  str_b += 'p'
  str_b = burger(str_b,level-1)
  str_b += 'B'
  return str_b


str_b = ''
N,X = map(int,input().split())
str_b = burger(str_b,N)
b_list = list(str_b)
eat_list = b_list[::-1]
eat_list = b_list[0:X]
print(eat_list.count('p'))

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
def dfs(s):
  if int(s) == 0:
    return [1]
  return [0] + dfs(s-1) + [1] + dfs(s-1) + [0]
a = dfs(n)
s = 0
for i in range(x):
  s += a[i]
print(int(s))

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache

@lru_cache(maxsize=1000)
def hum(n):
    if n==1:
        mylist=[]
        mylist.append(1)
        return mylist
    list2=[]
    list2.append(0)
    list2.extend(hum(n-1))
    list2.append(1)
    list2.extend(hum(n-1))
    list2.append(0)

    return list2

a,b=map(int,input().split())
list1=hum(a+1)
list3=list1[0:b]
print(list3.count(1))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
 
tmp=input()
n = int(tmp.split(" ")[0])
x = int(tmp.split(" ")[1])

l=[int(1)]

for i in range(n):
    l=[0]+l+[1]+l+[0]

y=int(0)

for i in range(x):
    y=y+l[i]

print(y)

Submission status: Time Limit Exceeded

Solution code:
def hum(n):
    if n==1:
        mylist=[]
        mylist.append(1)
        return mylist
    list2=[]
    list2.append(0)
    list2.extend(hum(n-1))
    list2.append(1)
    list2.extend(hum(n-1))
    list2.append(0)

    return list2

a,b=map(int,input().split())
list1=hum(a+1)
list3=list1[0:b]
print(list3.count(1))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np                                                                                                                                                           
N, X = input().split(" ")                                                                                                                                                    
N = int(N)                                                                                                                                                                   
X = int(X)                                                                                                                                                                   
                                                                                                                                                                             
def make_LN_hamburger(last_hamburger):                                                                                                                                       
    return [0] + last_hamburger + [1] + last_hamburger + [0]                                                                                                                 
                                                                                                                                                                             
hamburger = [1]                                                                                                                                                              
for i in range(N):                                                                                                                                                           
    hamburger = make_LN_hamburger(hamburger)                                                                                                                                 
                                                                                                                                                                             
ans = np.sum(np.array(hamburger[-X:]))                                                                                                                                       
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# Christmas 

N = list(map(int, (input().strip().split(' '))))
X = N[1]
N = N[0]

def burger(L):
  if L == 0:
    return 'P'
  else:
    return 'B' + burger(L-1) + 'P' + burger(L-1) + 'B'

b = burger(N)[0:X]
print(b.count('P'))

Submission status: Time Limit Exceeded

Solution code:
def get_lburger(l):
    lburger = [1]
    for i in range(l):
        lburger = [0] + lburger + [1] + lburger + [0]
    return lburger

if __name__ == "__main__":
    N, X = map(int, input().split())
    print(sum(get_lburger(N)[:X]))

Submission status: Time Limit Exceeded

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

def burger(n):
    return 'B' + burger(n - 1) + 'P' + burger(n - 1) + 'B' if n>0 else 'P'

print(burger(n)[:x].count('P'))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,x=[int(i) for i in input().split()]
burger="BAPAB"
for i in range(n-1):
    if(x<len(burger)):
        burger=burger[0:x]
    burger=burger.replace("A","BAPAB")
ans=0
burger=burger.replace("A","P")

ans=burger[0:x].count("P")
print(ans)

Submission status: Time Limit Exceeded

Solution code:
burgerList=[""]*51
def burger(level):
    if burgerList[level]=="":
        if level==0:
            burgerList[level]="P"
        else:
            burgerList[level]="B"+burger(level-1)+"P"+burger(level-1)+"B"
    return burgerList[level]
 
n,x=[int(x) for x in input().split()]
print(burger(n)[:x].count("P"))

Submission status: Time Limit Exceeded

Solution code:
def bu(n):
  if n == 0:
    return 'p'
  else:
    return 'b' + bu(n-1) + 'p' + bu(n-1) + 'b'

n, x = map(int, input().split())
#li = list(bu(n))
#print(li)

count = 0
for i in range(x):
  if bu(n)[i] == 'p':
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def bu(n):
  if n == 0:
    return 'p'
  else:
    return 'b' + bu(n-1) + 'p' + bu(n-1) + 'b'

n, x = map(int, input().split())
li = list(bu(n))
#print(li)

count = 0
for i in range(x):
  if li[i] == 'p':
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def bg(n:int):
    
    if n == 0:
        yield 'P'
        
    else:
        yield 'B'
        
        gen = bg(n-1)
        while True:
            try:
                yield next(gen)
            except:
                break

        
        yield 'P'
        
        gen = bg(n-1)
        while True:
            try:
                yield next(gen)
            except:
                break
        
        yield 'B'
        

n,x = li()

cnt = 0
ans = 0

s = bg(n)
while True:
    try:
        char = next(s)
        if char == 'P' and cnt < x:
            ans += 1
            
        cnt += 1
    except:
        break
            
print(ans)

Submission status: Time Limit Exceeded

Solution code:
barger = "P"
A,B = map(int,input().split())

def level(n):
    global A,B,barger
    if n > A:
        return 0
    barger = "B"+barger+"P"+barger+"B"
    return level(n+1)

level(1)
#print(barger)
print(barger[0:B].count("P"))

Submission status: Time Limit Exceeded

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

def burger(number):
  if number == 0:
    return 'P'
  if number < 0:
    return 0
  ret = 'B' + burger(number-1) + 'P' + burger(number-1) + 'B'
  return ret

burger_str = burger(N)
print(burger_str[0:X].count('P'))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,x=[int(i) for i in input().split()]
burger="BAPAB"
for i in range(n-1):
    burger=burger.replace("A","BAPAB")
ans=0
burger=burger.replace("A","P")

ans=burger[0:x].count("P")
#for i in range(len(burger)):
#    if(burger[i] == "P")
#    ans+=
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, X = map(int, input().split())
burger = ['P']
for i in range(N):
	burgernext = ['B'] + burger + ['P'] + burger +  ['B']
	burger = burgernext
eat = burger[-X:]
print(eat.count('P'))

Submission status: Time Limit Exceeded

Solution code:
N,Y=map(int,input().split())
L=['P']
for i in range(N):
  X=['B']
  X.extend(L)
  X.append('P')
  X.extend(L)
  X.extend('B')
  L=X
print(L[0:Y].count('P'))

Submission status: Time Limit Exceeded

Solution code:
pb_list = []
p_count = 0

def pb(n):
    if n == 0:
        pb_list.append('p')
        return
    elif n >= 0:
        pb_list.append('b')
        pb(n - 1)
        pb_list.append('p')
        pb(n - 1)
        pb_list.append('b')
    else:
        return

n, x = input().split(' ')
n = int(n)
x = int(x)
pb(n)

for i in range(x):
    if pb_list[i] == 'p':
        p_count = p_count + 1

print(p_count)

Submission status: Time Limit Exceeded

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

def burg(n):
    if n==0:
        return("P")
    else:
        return("B{0}P{1}B". format(burg(n-1), burg(n-1)))

B = list(burg(N))
#print(B)
count = 0
for i in range(X):
    if B[i]=="P":
        count+=1
        
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,X = map(int,input().split(" "))
def Lv(n):
    if n == 0:
        return "p"
    else:
        return "b"+Lv(n-1)+"p"+Lv(n-1)+"b"
bar = list(Lv(N))
barg = bar[0:X]
print(barg.count("p"))

Submission status: Time Limit Exceeded

Solution code:
def burger(level):
    if level==0:
        return "P"
    else:
        return "B"+burger(level-1)+"P"+burger(level-1)+"B"

n,x=[int(x) for x in input().split()]
print(burger(n)[:x].count("P"))

Submission status: Accepted

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

#lレベルバーガーの下からx層に含まれるパティーの数
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 count(l,x):
  if l==0:
    if x>=1:
      return 1
    else:
      return 0
  else:
    if x==1:
      return 0
    elif x<a[l-1]+2:
      return count(l-1,x-1)
    elif x==a[l-1]+2:
      return p[l-1]+1
    elif a[l]>x:
      return count(l-1,x-a[l-1]-2)+p[l-1]+1
    else:
      return p[l]
    
print(count(n,x))

Submission status: Accepted

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

sizes = [1]

for i in range(n):
    sizes.append(2*sizes[i]+3)

prev = {}

def solve(n, x):
    if (n, x) in prev:
        return prev[(n, x)]
    else:
        if n == 0:
            return 1 if x == 1 else 0
        else:
            ans = 0
            if x == sizes[n]:
                ans = 2*solve(n-1, sizes[n-1]) + 1
            else:
                mid = sizes[n]//2 + 1

                if x == mid:
                    ans = solve(n-1, sizes[n-1]) + 1
                elif x < mid:
                    ans = solve(n-1, x-1)
                else:
                    ans = solve(n-1, sizes[n-1]) + 1 + solve(n-1, x-mid)

            prev[(n, x)] = ans
            return ans

print(solve(n, x))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N, X = map(int, input().split())

layers = [1]
patties = [1]

for i in range(1, N+1):
	layer_i = 2 * layers[i-1] + 3
	patty_i = 2 * patties[i-1] + 1
	layers.append(layer_i)
	patties.append(patty_i)
	
def f(n, x):
	if x == 1:
		return 1 if n == 0 else 0
		
	elif 1 < x <= 1 + layers[n-1]:
		return f(n-1, x-1)
		
	elif x == 2 + layers[n-1]:
		return patties[n-1] + 1
		
	elif 2 + layers[n-1] < x <= 2 + 2 * layers[n-1]:
		return patties[n-1] + 1 + f(n-1, x-2-layers[n-1])
		
	else:
		return 2 * patties[n-1] + 1
		
print(f(N, X))

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


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

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

    ans = 0
    for _ in range(n):
        if x == 0:
            break
        if x >= pb[-2] + 2:
            x -= pb[-2] + 2
            ans += 1 + p[-2]
        else:
            x -= 1
        pb.pop(-1)
        p.pop(-1)

    if x >= 1:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
#
#
# @stop_watch
def solve(N, X):
    layer = [1]
    pate = [1]
    for _ in range(N):
        layer.append(layer[-1] * 2 + 3)
        pate.append(pate[-1] * 2 + 1)

    # print(layer[-1])
    # print(pate[-1])

    def burger(n, l):
        if layer[n] <= l:
            return pate[n]
        if l == 0:
            return 0
        re = 0
        if layer[n] // 2 + 1 <= l:
            re += pate[n - 1] + 1  # center pattie
            l -= layer[n] // 2 + 1
        else:
            l -= 1  # first bun
        re += burger(n - 1, l)
        return re

    print(burger(N, X))


if __name__ == '__main__':
    N, X = map(int, input().split())
    solve(N, X)

    # # test
    # from random import randint
    # from func import random_str
    # N, X = 3, 1
    # for i in range(1, 29 + 1):
    #     solve(N, i)

Submission status: Accepted

Solution code:
N,X=map(int,input().split())  #S=2**(N+2)-3
                  #P=2**(N+1)-1
def solve(N,X):
    if X==0:
        return 0
    if N==0:
        return X
    if X<2**(N+1)-1:
        return solve(N-1,X-1)
    elif X==2**(N+1)-1:
        return 2**N
    elif X<2**(N+2)-3:
        return 2**N+solve(N-1,X-2**(N+1)+1)
    else:
        return 2**(N+1)-1

print(solve(N,X))

Submission status: Accepted

Solution code:
def delete_head_zeros(n):
	n = str(n)
	l = len(n)
	if "." in n:
		l = n.find(".")
	head_zeros = 0
	for i in range(l - 1):
		if n[i] == "0":
			head_zeros += 1
		else:
			break

	return n[head_zeros:]

# compare a, b
# a, b: int or string
def bigint_compare(a, b):
	a = delete_head_zeros(a)
	b = delete_head_zeros(b)
	if len(a) > len(b):
		return 1
	elif len(a) < len(b):
		return -1
	else:
		if a > b:
			return 1
		elif a < b:
			return -1
		else:
			return 0

# calculate a + b
# a, b: int or string
def bigint_plus(a, b):
	a = str(a)
	b = str(b)

	d = max([len(a), len(b)])
	a = '0' * (d - len(a)) + a
	b = '0' * (d - len(b)) + b

	ans = ""
	carry = 0
	for i in range(d):
		s = int(a[-i-1]) + int(b[-i-1]) + carry
		carry = s // 10
		ans = str(s % 10) + ans
	else:
		if carry:
			ans = str(carry) + ans

	return ans

# calculate a - b
# a, b: int or string
def bigint_minus(a, b): 
	a = str(a)
	b = str(b)
	M = []
	m = []
	sign = ""

	if len(a) > len(b) or (len(a) == len(b) and a >= b):
		[M, m] = [a, b]
	else:
		[M, m] = [b, a]
		sign = "-"
	m = '0' * (len(M) - len(m)) + m

	ans = ""
	borrow = 0
	for i in range(len(M)):
		s = int(M[-i-1]) - int(m[-i-1]) - borrow
		if s < 0:
			borrow = 1
			s += 10
		else:
			borrow = 0
		ans = str(s) + ans

	return sign + delete_head_zeros(ans)

# calculate a * b
# a, b: int or string
def bigint_multiply(a, b):
	a = str(a)
	b = str(b)

	md = []
	for j in range(len(b)):
		carry = 0
		mj = ""
		for i in range(len(a)):
			m = int(a[-i-1]) * int(b[-j-1]) + carry
			carry = m // 10
			mj = str(m % 10) + mj
		else:
			if carry:
				mj = str(carry) + mj
		md.append(mj)

	ans = 0
	for k in range(len(md)):
		ans = bigint_plus(md[k] + "0" * k, ans)

	return ans


# calculate a / b to d digits after decimal point
# a, b, d: int or string
def bigint_divide(a, b, d = 0):
	a = str(a)
	b = str(b)
	d = int(d)
	if d < 0:
		d = 0

	ans = ""
	r = ""
	for i in range(len(a) + d):
		q = 0
		if i < len(a):
			r += a[i]
		elif i == len(a):
			ans += "."
			r += "0"
		else:
			r += "0"

		if bigint_compare(r, b) == -1:
			ans += str(q)
		else:
			while bigint_compare(r, b) >= 0:
				r = bigint_minus(r, b)
				q += 1
			ans += str(q)

	return delete_head_zeros(ans)

def main():
	N, X = input().split(" ")
	layer = [1]
	patties = [1]
	for i in range(int(N)):
		layer.append(bigint_plus(bigint_multiply(layer[-1], 2), 3))
		patties.append(bigint_plus(bigint_multiply(patties[-1], 2), 1))

	def count_patty(L, Y, P): # Y, P : bigint
		if L == 0:
			return bigint_plus(P, 1)
		center = bigint_divide(bigint_plus(layer[L], 1), 2)
		if Y == "1":
			return P
		elif Y == layer[L]:
			return bigint_plus(P, patties[L])
		elif bigint_compare(Y, center) == 0:
			return bigint_plus(bigint_plus(P, 1), patties[L - 1])
		elif bigint_compare(Y, center) == 1:
			return count_patty(L - 1, bigint_minus(Y, center), bigint_plus(bigint_plus(P, patties[L - 1]), 1))
		elif bigint_compare(Y, center) == -1:
			return count_patty(L - 1, bigint_minus(Y, 1), P)

	print(count_patty(int(N), X, "0"))

main()

Submission status: Accepted

Solution code:
#再帰の深さが1000を超えそうなときはこれをやっておく
import sys
sys.setrecursionlimit(10**7)

n,x=map(int,input().split())
a=[0]*(n+1)
p=[0]*(n+1)
a[0]=1
p[0]=1
for i in range(n):
  a[i+1]=2*a[i]+3
  p[i+1]=2*p[i]+1
  
def func(i,x):
  if i==0:
    if x<=0:
      return 0
    elif x>=1:
      return 1
  mid=(a[i]+1)//2
  if mid==x:
    return p[i-1]+1
  elif mid>x:
    return func(i-1,x-1)
  else:
    return p[i-1]+1+func(i-1,x-mid)


print(func(n,x))

Submission status: Accepted

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

a, b = [1], [1]

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

def cal(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1
    val = (a[n]+1)//2

    if x < val:
        return cal(n-1, x-1)
    elif x == val:
        return b[n-1]+1
    elif x > val:
        return b[n-1]+1+cal(n-1, x-val)

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

Submission status: Accepted

Solution code:

def resolve():
    N, X = map(int, input().split())

    As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
    Ps = [1]  # レベルiバーガーのパティの総数

    for i in range(N):
        As.append(As[i] * 2 + 3)  # レベルが1上がると、総数は2倍+3になる
        Ps.append(Ps[i] * 2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

    def f(n, x):
        if n == 0:
            return 0 if x <= 0 else 1
        mid = (As[n] + 1) // 2

        # バーガーの真ん中にはパティがある。そのパティを含むかの場合分けをする
        if x < mid:
            return f(n - 1, x - 1)
        elif x == mid:
            return Ps[n - 1] + 1
        elif x > mid:
            return Ps[n - 1] + 1 + f(n - 1, x - mid)

    ans = f(N, X)

    print(ans)


if __name__ == "__main__":
    resolve()

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):
    P[i]=2*P[i-1]+1
    A[i]=2*P[i]-1

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

print(f(N,X))

Submission status: Accepted

Solution code:
import sys
import collections

sys.setrecursionlimit(10**6)

def f(X:int, N:int):
    if N == 0:
        return 1
    if N == 1:
        if X == 1:
            return 0
        elif X in [2, 3, 4]:
            return X-1
        else:
            return 3
    l = sum(L[N-1])
    if X == 1:
        return 0
    elif 1 < X <= l+1:
        return f(X-1, N-1)
    elif X == l+2:
        return L[N-1][1] + 1
    elif l+2 < X <= sum(L[N]):
        return L[N-1][1] + 1 + f(X-2-l, N-1)
    else:
        return 2 * L[N-1][1] + 1

def main():
    global L
    N, X = map(int, input().split())
    L = [(0, 1)]
    for i in range(N):
        b, p = L[i]
        b = 2*b + 2
        p = 2*p + 1
        L.append((b, p))
    ans = f(X, N)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
L=[[1,1] for _ in range(N+1)]
i=0
while i+1<=N:
    L[i+1][0]=L[i][0]*2+1
    L[i+1][1]=L[i+1][0]*2-1
    i+=1

xx=[[1,1,1,1,1]for _ in range(N+1)]
i=0
while i+1<=N:
    xx[i+1][1]=L[i][1]+1
    xx[i+1][2]=L[i][1]+2
    xx[i+1][3]=2*L[i][1]+2
    xx[i+1][4]=2*L[i][1]+3
    i+=1

ans=0
while N>0:
    if xx[N][0]==X:
        break
    elif xx[N][1]>=X:
        N-=1
        X-=1
    elif xx[N][2]==X:
        ans+=1+L[N-1][0]
        break
    elif xx[N][3]>=X:
        ans+=1+L[N-1][0]
        X-=xx[N][2]
        N-=1
    else:
        ans+=1+2*L[N-1][0]
        break
    if N==0:
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
N, X = map(int, input().split())
a = [0] * (N)
p = [0] * N
a[0] = 1
p[0] = 1
for i in range(1, N):
    a[i] = a[i-1]*2 + 3
    p[i] = p[i-1]*2 + 1
@lru_cache(maxsize=1000)
def f(n, x):
    if n == 0 and x == 0:
        return 0
    elif n == 0:
        return 1
    if 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])
    else:
        return 2*p[n-1]+1
print(f(N, X))

Submission status: Accepted

Solution code:
import sys
from sys import exit
from collections import deque
from copy import deepcopy
from bisect import bisect_left, bisect_right, insort_left, insort_right
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from functools import reduce
from math import gcd, sin, cos, tan, asin, acos, atan, degrees, radians

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def powmod(n,i,mod=MOD):
    return pow(n,mod-1+i,mod) if i<0 else pow(n,i,mod)
def div2(x):
    return x.bit_length()
def div10(x):
    return len(str(x))-(x==0)
def intput():
    return int(input())
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x,d=1):
        self.setdefault(x,0)
        self[x] += d
    def list(self):
        l = []
        for k in self:
            l.extend([k]*self[k])
        return l
class comb():
    def __init__(self, n, mod=None):
        self.l = [1]
        self.n = n
        self.mod = mod
    def get(self,k):
        l,n,mod = self.l, self.n, self.mod
        k = n-k if k>n//2 else k
        while len(l)<=k:
            i = len(l)
            l.append(l[i-1]*(n+1-i)//i if mod==None else (l[i-1]*(n+1-i)*powmod(i,-1,mod))%mod)
        return l[k]
def pf(x,mode='counter'):
    C = counter()
    p = 2
    while x>1:
        k = 0
        while x%p==0:
            x //= p
            k += 1
        if k>0:
            C.add(p,k)
        p = p+2-(p==2) if p*p<x else x
    if mode=='counter':
        return C
    S = set([1])
    for k in C:
        T = deepcopy(S)
        for x in T:
            for i in range(1,C[k]+1):
                S.add(x*(k**i))
    if mode=='set':
        return S
    if mode=='list':
        return sorted(list(S))

######################################################

N,X=mint()
ans=0
size=[0]*51
size[0]=(1,1)
for i in range(1,51):
    size[i]=(2*size[i-1][0]+3, 2*size[i-1][1]+1)

def rec(L):
    global X,ans
    if X==0:
        return
    if L==0:
        X-=1
        ans+=1
    else:
        X-=1
        if X<size[L-1][0]:
            rec(L-1)
        else:
            X-=size[L-1][0]
            ans+=size[L-1][1]
        if X==0:
            return
        X-=1
        ans+=1
        if X<size[L-1][0]:
            rec(L-1)
        else:
            X-=size[L-1][0]
            ans+=size[L-1][1]
        if X==0:
            return
        X-=1
    
rec(N)
print(ans)

Submission status: Accepted

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

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

    ans = 0
    for _ in range(n):
        if x == 0:
            break
        if x >= pb[-2] + 2:
            x -= pb[-2] + 2
            ans += 1 + p[-2]
        else:
            x -= 1
        pb.pop(-1)
        p.pop(-1)

    if x >= 1:
        ans += 1

    print(ans)

main()

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
b = 1
p = 1
for i in range(n):
    b = 2 * b + 3
    p = 2 * p + 1
x -= 1
b -= 1
ans = 0
while True:
    if x == 0:
        if b == 0:
            ans += 1
        break
    elif x == b:
        ans += p
        break
    elif x == b // 2:
        ans += p // 2 + 1
        break
    elif 0 < x < b // 2:
        x -= 1
    else:
        x -= b // 2 + 1
        ans += p // 2 + 1
    b = (b - 3) // 2
    p = (p - 1) // 2
print(ans)

Submission status: Accepted

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

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

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= size[N-1] + 1:
        return f(N-1, X-1)
    elif X == size[N-1] + 2:
        return patty[N-1] + 1
    elif X >= size[N-1] + 3:
        return patty[N-1] + 1 + f(N-1, X-size[N-1]-2)
print(f(N,X))

Submission status: Accepted

Solution code:
import sys
import heapq
from functools import lru_cache
sys.setrecursionlimit(10000)

# \n
def input():
    return sys.stdin.readline().rstrip()


def level(n, k):
    number = 2 ** (n + 1) - 3  # 一個レベル下のやつの数
    cn = 2**(n+2) -3
    if n == 0:
        return 1
    elif k==cn:
        return (2**(n+1) -1)

    else:
        if k == 1:
            return 0
        elif k <= 1 + number:
            return level(n - 1, k - 1)
        elif k == 2 + number:
            return level(n - 1, number) + 1
        else:
            return 1 + level(n - 1, number) + level(n - 1, min(number, k - number - 2))



def main():

    n,k=map(int,input().split())
    print(level(n,k))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**5)
N, X = map(int,input().split())
l = [1]
for i in range(N):
    l.append(2*l[-1]+3)
d = {}
def f(n,x):
    if (n,x) in d:
        return d[(n,x)]
    if n == 0:
        ans = 1
    elif x == 1:
        ans = 0
    elif x <= l[n-1]+1:
        ans = f(n-1,x-1)
    elif x == l[n-1]+2:
        ans = f(n-1,l[n-1])+1
    elif x <= 2*l[n-1]+2:
        ans = f(n-1, l[n-1])+1+f(n-1, x-l[n-1]-2)
    else:
        ans = 2*f(n-1, l[n-1])+1
    d[(n,x)] = ans
    return ans
print(f(N, X))

Submission status: Accepted

Solution code:
import sys
# sys.setrecursionlimit(100000)
from functools import lru_cache


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n, x = input_int_list()
    layer_size = [1]
    p_cnt = [1]

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

    @lru_cache(None)
    def L(level, x):
        if x == 1:
            if level == 0:
                return 1
            else:
                return 0
        l = layer_size[level - 1]
        p = p_cnt[level - 1]
        if x <= l + 1:
            return L(level - 1, x - 1)
        elif x == l + 2:
            return p + 1
        elif x <= 2 + l * 2:
            return p + 1 + L(level - 1, x - l - 2)
        else:
            return 2 * p + 1
    print(L(n, x))
    return


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[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<=a[n-1]+1:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-a[n-1]-2)+1
print(f(N,X))

Submission status: Accepted

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

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

def f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + a[N-1]:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-a[N-1])

print(f(N, X))