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: Wrong Answer

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

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

Submission status: Wrong Answer

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

def f(n, x):
    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 + ls[n-1] // 2 + 1
    elif x < ls[n]:
        return 1 + ls[n-1] // 2 + 1 + f(n-1, x - ls[n-1] - 2)
    else:
        return ls[n] // 2 + 1
res = f(n, x)
print(res)

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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(50,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: Wrong Answer

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(50,0,-1):
        if x>=pre_total[i]-1:
            ans+=pre_P[i]
            print(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: Wrong Answer

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]
    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]
    
    n,x=inpm()
    ans=0
    for i in range(49,-1,-1):
        if x>=pre_total[i]:
            x-=pre_total[i]
            ans+=pre_P[i]
    print(ans)
        
    

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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 == 1:
    ans += 0
elif X == 2**(N+1)-1:
    ans += 2**N
else:
    ans += 2**(N+1)-1
print(ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right

N,X=map(int,input().split())
M=[0]*(N+1)
M[0]=1
P=[0]*(N+1)
P[0]=1

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

X-=1
C=0

while X>0:
    b=bisect_right(M,X)-1
    X-=M[b]
    C+=P[b]
    if X>0:
        X-=1
        C+=1
    if X>0:
        X-=1

print(C)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def solve(N: int, X: int):
    # amount[i] = level iバーガーの総数
    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 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: Wrong Answer

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

Submission status: Wrong Answer

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 += items
			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(i,j))
#print(getItems(2))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
hight, paty = [0]*51, [0]*51
hight[0] = 1
paty[0] = 1

for i in range(1, 51):
	hight[i] = 2*hight[i-1] + 3
	paty[i] = 2*paty[i-1] + 1

def f(n, x):
	if x == 0: return 0
	elif n == 0: return 1
    
	if x < hight[n]//2:
		return f(n-1, x-1)
	if x >= hight[n]//2 :
		return paty[n-1] + 1 + f(n-1, x-hight[n-1]-2)

print(f(N, X))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from sys import stdin
N, X = [int(x) for x in stdin.readline().rstrip().split()]

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


def solve(n, x):
    if x == 1:
        return 0
    elif 1 < x <= 1+heights[n-1]:
        return solve(n-1, x-1)
    elif x == 2+heights[n-1]:
        return 1+putties[n-1]
    elif 2+heights[n-1] < x <= 2+2*heights[n-1]:
        return putties[n-1]+1+solve(n-1,x-2-heights[n-1]) 
    elif x == 3+2*heights[n-1]:
        return 2*putties[n-1]+1
print(solve(N, X))

Submission status: Wrong Answer

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

BP = [1]
P = [1]

for i in range(n):
  BP.append(BP[i]*2+3)
  P.append(P[i]*2+1)
  
def check_P_num(n, x):
  
  if n==0:
    return 1
  
  if x==BP[n]:
    return(P[n])
  elif x==1:
    return(0)
  elif x == BP[n-1]+2:
    return(P[n-1]+1)
  elif x <= BP[n-1]+1:
    return(check_P_num(n-1, x-1))
  else:
    return(check_P_num(n-1, x-BP[n-1]-1)+P[n-1])
  
  
print(check_P_num(n, x))

Submission status: Wrong Answer

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

BP = [1]
P = [1]

for i in range(n):
  BP.append(BP[i]*2+3)
  P.append(P[i]*2+1)
  
def check_P_num(n, x):
  
  if n==0:
    return 1
  
  if x==BP[n]:
    return(P[n])
  elif x==1:
    return(0)
  elif x == BP[n-1]+2:
    return(P[n-1]+1)
  elif x <= BP[n-1]+1:
    return(check_P_num(n-1, x-1))
  else:
    return(check_P_num(n-1, x-BP[n-1])+P[n-1])
  
  
print(check_P_num(n, x))

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
dp = [None] * (n+1)

def getBurger(n):
    if n == 0:
        return 'P'
    else:
        return 'B' + getBurger(n-1) + 'P' + getBurger(n-1) + 'B'

for i in range(n+1):
    if i == 0:
        dp[i] = 'P'
    else:
        dp[i] = 'B' + dp[i-1] + 'P' + dp[i-1] + 'B'

#print(getBurger(n))

#print(dp[n])
#print(dp[n][:x+1])

print(dp[n][:x+1].count('P'))

Submission status: Wrong Answer

Solution code:
import sys
n, x = map(int, input().split())
ans = 0
layer = [1 for _ in range(n+1)]
patty = [1 for _ in range(n+1)]
for i in range(1,n+1):
    layer[i] = 2*layer[i-1]+3
    patty[i] = 2*patty[i-1]+1
def eat(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    elif x <= 1+layer[n-1]:
        return eat(n-1, x-1)
    elif x == 2+layer[n-1]:
        return patty[n-1]+1
    elif x <= 2+2*layer[n-1]:
        return patty[n-1]+1+eat(n-1, x-2-layer[n-1])
    else:
        return 2*patty[n-1]
ans = eat(n, x)
print(ans)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
p, q = [1] + [0] * n, [1] + [0] * n

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

def rec(i, x):
    if i == 0: return 1 if x >= 1 else 0
    mid = q[i] // 2
    if x < mid:
        return rec(i-1, x-1)
    else:
        return p[i-1] + 1 + rec(i-1, x-mid-1)

print(rec(n, x))

Submission status: Wrong Answer

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if bothCount(i) != pattiesCount(i) + bunsCount(i):
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat == 1)
    both = bothCount(level - 1)
    patties = pattiesCount(level - 1)
    if eat == both + 2:
        return 1 + patties
    if eat > both + 1:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Wrong Answer

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if bothCount(i) != pattiesCount(i) + bunsCount(i):
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat == 1)
    both = bothCount(level)
    patties = pattiesCount(level)
    if eat == both + 2:
        return 1 + patties
    if eat > both + 1:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Wrong Answer

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if bothCount(i) != pattiesCount(i) + bunsCount(i):
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat == 1)
    both = bothCount(level)
    patties = pattiesCount(level)
    if eat == both + 2:
        return 1 + patties
    if eat > both:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Wrong Answer

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if bothCount(i) != pattiesCount(i) + bunsCount(i):
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat == 1)
    both = bothCount(level)
    patties = pattiesCount(level)
    if eat == both + 3:
        return 1 + patties
    if eat > both:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Wrong Answer

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

pattiesCount = lambda level: (1 << (level + 1)) - 1
bunsCount = lambda level: (1 << (level + 1)) - 2
bothCount = lambda level: (1 << (level + 2)) - 3

# for i in range(51):
#     if bothCount(i) != pattiesCount(i) + bunsCount(i):
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

def doit(level, eat):
    if level == 0:
        return int(eat == 1)
    both = bothCount(level)
    patties = pattiesCount(level)
    if eat == both + 1:
        return 1 + patties
    if eat > both:
        return 1 + patties + doit(level - 1, eat - 2 - both)
    return doit(level - 1, eat - 1)

print(doit(n, eat))

Submission status: Wrong Answer

Solution code:
import os, sys, re, math

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

memo_length = [0 for i in range(51)]
memo_patties = [0 for i in range(51)]
memo_length[0] = 1
memo_patties[0] = 1

for i in range(1,51):
    memo_length[i] = memo_length[i-1] * 2 + 3
    memo_patties[i] = memo_patties[i-1] * 2 + 1

def doit(level,x):
    if x == 0:
        return 0
    if x >= memo_length[level]:
        return memo_patties[level]

    tmp = memo_length[level-1]
    ret = 0

    if x >= 1:
        ret += doit(level-1, x-1)
    if x >= tmp + 2:
        ret += 1
        ret += doit(level-1, x-tmp-2)

    return ret

print(doit(N,X-1))

Submission status: Wrong Answer

Solution code:
n, k = list(map(int, input().split(' ')))
lens = {0: 1}
for i in range(1, 51):
  lens[i] = lens[i-1] * 2 + 3
memo = {}

def sumP(level, index):
  key = (level, index)
  if key in memo:
    return memo[key]
  if level == 0:
      memo[key] = int(index == 1)
  elif index < lens[level] // 2 + 1:   # |Bxxxxxxx|xxxxxPxxxxxxxxxxB
    memo[key] = sumP(level-1, index-1)
  elif index <= lens[level] // 2 + 1:  # |BxxxxxxxxxxxxP|xxxxxxxxxxB
    memo[key] =  + sumP(level-1, lens[level-1])
  else:                                # |BxxxxxxxxxxxxPxxxxxxxx|xxB
    memo[key] = sumP(level-1, lens[level-1]) + 1 + sumP(level-1, min(lens[level-1], index-lens[level-1]-2))
  return memo[key]

print(sumP(n, k))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
layers = 1
P = 1
B = 0
d = dict()
d[0] = (P, B)
for n in range(1, N + 1):
    layers = 1 + layers + 1 + layers + 1
    P = P + 1 + P
    B = 1 + B + B + 1
    d[n] = (P, B)

#print(layers)
n = N
x = X
start = 0
end = layers
ret_p = 0
while n > 1:
    half = (start + end) // 2
    if x == half + 1:
        ret_p += d[n - 1][0]
        ret_p += 1
        break

    if x == half:
        ret_p += d[n - 1][0]
        break

    if x < half:
        x -= 1
    else:
        ret_p += d[n - 1][0]
        ret_p += 1
        x -= half + 1
    end = (end - 3) // 2
    n -= 1
 
print(ret_p)

Submission status: Wrong Answer

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

burgersize = [1]
beef_level = [2**i - 1 for i in range(1, n+2)]

a = 1
for i in range(n):
    a = 2*a + 3
    burgersize.append(a)


def eat(level, x):
    size = burgersize[level]
    half = (size + 1) // 2
    quarter = (half + 1) // 2
    three_quarter = (size + half) // 2

    beef = beef_level[level]

    if x >= size - 1:
        return beef

    elif x <= level:
        return 0

    elif level < x < quarter:
        return eat(level-2, x-1)

    elif x == quarter:
        return beef_level[level-2] + 1

    elif quarter < x < half:
        return beef_level[level-2] + eat(level-2, x-quarter)

    elif x == half:
        return beef//2 + 1

    elif half < x < three_quarter:
        return beef//2 + 1 + eat(level-2, x-half)

    elif x == three_quarter:
        return beef//2 + 1 + beef_level[level-2] + 1

    elif three_quarter < x < size - 1:
        return beef//2 + 1 + beef_level[level-2] + 1 + eat(level-2, x-three_quarter)


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

Submission status: Wrong Answer

Solution code:
N, X = [int(x) for x in input().split()]
h = [1]
b = [1]
for i in range(N):
    h.append(3 + h[i] * 2)
    b.append(1 + b[i] * 2)
def rec(n: int, x: int):
    if (n == 0):
        return 1 if x == 1 else 0
    mid = 1 + h[n-1] + 1
    if (x < mid):
        return rec(n-1, x-1)
    if (x == mid):
        return b[n-1] + 1
    if (mid < x):
        return b[n-1] + 1 + rec(n-1, x-mid)
print(rec(N, X))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
p=[0]*51
b=[0]*51
p[0]=1
for i in range(50):
    p[i+1]=2*p[i]+1
    b[i+1]=2*b[i]+2
def dfs(n,x):
    if x<=n:
        return 0
    if n==0:
        return 1
    z=p[n]+b[n]
    if z//2==x:
        return p[n-1]
    elif z//2+1==x:
        return p[n-1]+1
    elif z//2+1<x:
        return p[n-1]+1+dfs(n-1,x-z//2-1-1)
    else:
        return dfs(n-1,x-1)
print(dfs(n,x))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
p=[0]*51
b=[0]*51
p[0]=1
for i in range(50):
    p[i+1]=2*p[i]+1
    b[i+1]=2*b[i]+2
def dfs(n,x):
    if x<=n:
        return 0
    if n==0:
        return 1
    z=p[n]+b[n]
    if z//2==x:
        return p[n-1]
    elif z//2+1==x:
        return p[n-1]+1
    elif z//2+1<x:
        return p[n-1]+1+dfs(n-1,x-z//2-1)
    else:
        return dfs(n-1,x)
print(dfs(n,x))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
p=[0]*51
b=[0]*51
p[0]=1
for i in range(50):
    p[i+1]=2*p[i]+1
    b[i+1]=2*b[i]+2
def dfs(n,x):
    if x<=n:
        return 0
    if n==0:
        return 1
    z=p[n]+b[n]
    if z//2==x:
        return p[n-1]
    elif z//2+1==x:
        return p[n-1]+1
    elif z//2+1<x:
        return p[n-1]+dfs(n-1,x-z//2-1)
    else:
        return dfs(n-1,x)
print(dfs(n,x))

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
# D - Christmas

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

height = [1] # レベルiバーガーの高さ
for _ in range(N):
    height.append(height[-1]*2 + 3)
    
patty = [1] # レベルiバーガーに含まれるパティの総数
for _ in range(N):
    patty.append(patty[-1]*2 + 1)

def dp(n,x): # レベルnバーガーの下からx個の層に含まれるパティの数
    if x == 1:
        return 0
    elif x <= 1 + height[n-1]:
        return dp(n-1, x-1)
    elif x == 2 + height[n-1]:
        return patty[n-1] + 1
    elif x <= height[n] - 1:
        return patty[n-1] + 1 + dp(n-1, x - (height[n-1] + 2))
    else:
        return patty[n]
    
print(dp(N,X))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
nx = input()
nx = nx.split()
n = int(nx[0])
x = int(nx[1])
burger = "BPPPB"
for i in range(n-1):
  burger = "B" + burger + "P" + burger + "B"
print(burger[:x-1])

Submission status: Wrong Answer

Solution code:
nx = input()
nx = nx.split()
n = int(nx[0])
x = int(nx[1])
burgers = [None] * 51
burgers[0] = "P"
burgers[1] = "BPPPB"
burgers[2] = "BBPPPBPBPPPBB"
i = 3
while i<=n:
  burgers[i] = "B" + burgers[i-1] + "P" + burgers[i-1] + "B"
  i+=1
result = burgers[n][:x-1]
print(result.count("P"))

Submission status: Wrong Answer

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

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

#レベルnバーガーの構造は、1,2^(n+1)-3,1,2^(n+1)-3,1

ans = 0
x2 = x
k=n
while True:
  thk = [1,2**(k+1)-3,1,2**(k+1)-3,1]
  pc = [0,2**k-1,1,2**k-1,1]
  for i in range(5):
    x2-=thk[i]
    if x2<0:
      x2+=thk[i]
      k-=1
      break
    elif x2==0:
      ans+=pc[i]
      print(ans)
      exit()
    else:
      ans+=pc[i]

Submission status: Wrong Answer

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

burger = [1]*(n+1)
patty = [1]*(n+1)

stopped = 0
for i in range(1,n):
	burger[i] = 2*burger[i-1]+3
	patty[i] = 2*patty[i-1]+1
	
def solve(n, x):
	if n == 0:
		if x == 0:
			return 0
		else:
			return 1
	elif x == 0:
		return 0
	elif x == burger[n]:
		return patty[n]
	elif x == burger[n-1]+1:
		return patty[n-1]
	elif x == burger[n-1]+2:
		return patty[n-1]+1
	elif x < burger[n-1]+2:
		return solve(n-1, x-1)
	elif x > burger[n-1]+2:
		return solve(n-1, x-burger[n-1]-2)+patty[n-1]+1

print(solve(n, x))

Submission status: Wrong Answer

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

burger = [1]*(n+1)
patty = [1]*(n+1)

stopped = 0
for i in range(1,n):
	burger[i] = 2*burger[i-1]+3
	patty[i] = 2*patty[i-1]+1
	
def solve(n, x):
	if x == 0:
		return 0
	elif x == burger[n]:
		return patty[n]
	elif x == burger[n-1]+1:
		return patty[n-1]
	elif x == burger[n-1]+2:
		return patty[n-1]+1
	elif x < burger[n-1]+2:
		return solve(n-1, x-1)
	elif x > burger[n-1]+2:
		return solve(n-1, x-burger[n-1]-2)+patty[n-1]+1

print(solve(n, x))

Submission status: Wrong Answer

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

burger = [1]*(n+1)
patty = [1]*(n+1)

stopped = 0
for i in range(1,n):
	burger[i] = 2*burger[i-1]+3
	patty[i] = 2*patty[i-1]+1
	
def solve(n, x):
	if x == 0:
		return 0
	elif x == burger[n]:
		return patty[n]
	elif x == burger[n-1]+2:
		return patty[n-1]+1
	elif x < burger[n-1]+2:
		return solve(n-1, x-1)
	elif x > burger[n-1]+2:
		return solve(n-1, x-burger[n-1]-2)+patty[n-1]+1

print(solve(n, x))