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:
n,x = input().split()
n = int(n)
x = int(x)
num = [0 for i in range(n)]
memo = [[0,0] for i in range(n)]
memo[0][0] = 1
memo[0][1] = 1
for i in range(n-1):
    memo[i+1][0] = 2 * memo[i][0] + 1
    memo[i+1][1] = 2 * memo[i][1] + 3
sum = 0
while (n >= 0 and x >= 0):
    if x <= 1 + memo[n-1][1]:
        n -= 1
        x -= 1
    elif x == 2 + memo[n-1][1]:
        sum += 1
        break
    else:
        x = x - memo[n-1][1] - 2
        n -= 1
        sum += (memo[n][0] + 1)
print(sum)

Submission status: Wrong Answer

Solution code:



n, x = (int(x) for x in input().split())

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

total = 0
remain = x

def eat(n):

    global total
    global f
    global remain
    if n <0:
        return
    if remain == 0:
        return
    if f[n] <= remain:
        total += g[n]
        remain -= f[n]
        return
    if f[n] > remain:
        remain -=1
        if f[n-1] > remain:
            eat(n-1)
        else:
            total += g[n-1]
            remain -= f[n-1]
            total += 1
            remain -= 1
            eat(n-1)

eat(n)
print(total)

Submission status: Wrong Answer

Solution code:
import sys


def num_patty(level):
    return 2 ** (level + 1) - 1


def num_all(level):
    return 2 ** (level + 2) - 3


def total_patty(n, x):
    res = 0
    pos = x - 1
    for cur_level in range(1, n + 1)[::-1]:
        # print("L = {}, P = {}, R = {}".format(cur_level, pos, res), file=sys.stderr)
        prev_level_total = num_all(cur_level - 1)
        cur_level_total = num_all(cur_level)
        if pos == 0:
            # left bread
            break
        elif 1 <= pos <= prev_level_total:
            # left block
            pos -= 1
            continue
        elif pos == prev_level_total + 1:
            # middle patty
            res += num_patty(cur_level - 1) + 1
            return res
        elif prev_level_total + 2 <= pos <= cur_level_total - 2:
            # right block
            res += num_patty(cur_level - 1) + 1
            pos -= prev_level_total + 2
            continue
        else:
            # right bread
            res += num_patty(cur_level)
    return res


def main():
    n, x = (int(z) for z in input().split())
    res = total_patty(n, x)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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")
print(burger)
print(burger[1])

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

Submission status: Wrong Answer

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

def f(n):
    return 4 * pow(2, n) - 3
def g(n):
    return pow(2, n+1) - 1

def ss2(k, n):
    nn = f(n)
    cc = (nn//2) + 1
    if k == 1:
        return 0
    if k > nn:
        return g(n) 
    elif k == cc:
        return g(n-1) + 1  
    elif k > cc:
        return g(n-1) + 1 + ss2(k-cc, n-1)
    elif k < cc:
        return ss2(k-1, n-1)

def search(k, n):
    nn = f(n)
    cc = (nn//2) + 1
    if k == 1 or k == nn:
        return "P"
    elif k == cc:
        return "B"
    elif k > cc:
        return search(k - cc, n-1)
    elif k < cc:
        return search(k - 1, n-1)


print(ss2(X, N))

Submission status: Wrong Answer

Solution code:
import sys


def num_patty(level):
    return 2 ** (level + 1) - 1


def num_all(level):
    return 2 ** (level + 2) - 3


def total_patty(n, x):
    res = 0
    pos = x - 1
    for cur_level in range(1, n + 1)[::-1]:
        # print("L = {}, P = {}, R = {}".format(cur_level, pos, res), file=sys.stderr)
        prev_level_total = num_all(cur_level - 1)
        cur_level_total = num_all(cur_level)
        if pos == 0:
            # bread, do nothing
            break
        elif 1 <= pos <= prev_level_total:
            # left block
            pos -= 1
            continue
        elif pos == prev_level_total + 1:
            # middle patty
            res += num_patty(cur_level - 1) + 1
            return res
        elif prev_level_total + 2 <= pos <= cur_level_total - 2:
            # right block
            res += num_patty(cur_level - 1) + 1
            pos -= prev_level_total + 2
            continue
    return res


def main():
    n, x = (int(z) for z in input().split())
    res = total_patty(n, x)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

f = [[0, 0] for i in range(N + 1)]

# 総数, パティ
f[0] = [1, 1]
for i in range(1, N + 1):
    f[i][0] = 2 * f[i - 1][0] + 3
    f[i][1] = 2 * f[i - 1][1] + 1

"""
for i in range(0, N + 1):
    print(f[i][0], f[i][1])
"""

leftA = 0
leftB = 0

ans = 0

for i in range(N, 0, -1):
    if leftA + 1 == X:
        # finish
        ans = leftB
        break
    elif leftA + 1 + f[i-1][0] == X:
        # finish
        ans = leftB + f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] > X:
        leftA = leftA + 1
        leftB = leftB
    elif leftA + 1 + f[i-1][0] + 1 == X:
        # finish
        ans = leftB + 1 + f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] == X:
        # finish
        ans = leftB + 1 + 2 * f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] > X:
        leftA = leftA + 1 + f[i-1][0] + 1
        leftB = leftA + 1 + f[i-1][0]
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] + 1 == X:
        # finish
        ans = leftB + 1 + 2 * f[i-1][1]
        break
    # print(leftA, leftB)

print(ans)

Submission status: Wrong Answer

Solution code:
def subsolve(n, x):
    if(x <= 1):
        return 0
    L1 = (1 << (n + 1)) - 3
    Ps = (1 << n) - 1
    if(x >= 2 * L1 + 2):
        return 2 * Ps + 1
    if(x > L1 + 2):
        return Ps + subsolve(n -1, x - L1 - 2) + 1
    if(x == L1 + 2):
        return Ps + 1
    return subsolve(n - 1, x - 1)
if __name__ == '__main__':
    n, x = map(int, input().split())
    print(subsolve(n, x))

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
a = ["P"]
def b(L):
    if L != 0:
        c = ["B"]
        return c+b(L-1)+a+b(L-1)+c
    else :
        return a
j = b(N)
q = j[:X]
q.count("P")

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

burgersize, pnum = [1], [1]
for i in range(N):
    burgersize.append(burgersize[-1] * 2 + 3)
    pnum.append(pnum[-1] * 2 + 1)

def count_p(level, X):
    if level == 0:
        return 1
    # elif X == burgersize[level]:
    #     return pnum[level]
    elif X == 1:
        return 0
    elif X < (burgersize[level] - 1) // 2:
        return count_p(level - 1, X - 1)
    elif X == (burgersize[level] - 1) // 2:
        return count_p(level - 1, X - 1) + 1
    elif X > (burgersize[level] - 1) // 2:
        return pnum[level - 1] + 1 + count_p(level - 1, X - (burgersize[level] - 1) // 2 - 1)

    return None

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
number = 0
count = 0
def paty(n):
  global number,count,X
  if n == 0:
    number+=1
    count+=1
    if count>=X:
      print(number)
      exit()
  else:
    count+=1
    if count>=X:
      print(number)
      exit()
    paty(n-1)
    number+=1
    count+=1
    if count>=X:
      print(number)
      exit()
    paty(n-1)
    count+=1
    if count>=X:
      print(paty)
      exit()
paty(N)

Submission status: Wrong Answer

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

def solve():
    n, x = map(int, stdin.readline().split())
    items = []
    items.append([1,1])
    for i in range(1,n+1):
        items.append([items[-1][0]*2+3, items[-1][1]*2+1])
    
    ans = 0
    p = n
    while x:
        half = (items[p][0]+1)//2
        if x>=half:
            ans += items[p-1][1]+1
            x -= half
        else:
            x -= 1
        p -= 1
    print(ans)

solve()

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

Solution code:
def func(N, X):
	global l, p

	if l[N] == X:
		return p[N]
	
	if X == 1:
		return 0
	temp = 1 + l[N - 1]
	s = 0
	if X <= temp:
		return func(N - 1, X - 1)
	temp += 1
	if X == temp:
		return p[N - 1] + 1
	temp += l[N - 1]
	if X <= temp:
		return func(N - 1, X - 2 - l[N - 1]) + p[N - 1] + 1
	return 2 * p[N - 1] + 1
	
		
N, X = map(int, input().split())

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

l[0] = 1
p[0] = 1

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

ans = func(N, X)

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
B = [0] * (N + 1)
P = [1] * (N + 1)
for i in range(N):
  B[i + 1] = 2 * B[i] + 2
  P[i + 1] = 2 * P[i] + 1
S = [B[i] + P[i] for i in range(N + 1)]
cnt = 0
def burg(L, X):
  cnt = 0
  if L == 0:
    return 1
  elif X <= L:
    return 0
  elif X <= S[L - 1] + 1:
    return burg(L - 1, X - 1)
  elif X == S[L]:
    return P[L]
  else:
    return P[L - 1] + 1 + burg(L - 1, X - S[L - 1] - 2)
print(burg(N, X))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
A = [1] * 55
memo = {}


def func(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 1
    if (n, x) in memo:
        return memo[(n, x)]

    if x < 1 + A[n-1]:
        memo[(n, x)] = func(n-1, x-1)
        return memo[(n, x)]
    if 1 + A[n-1] <= x:
        memo[(n, x)] = func(n-1, A[n-1]) + func(n-1, x-A[n-1]-2) + 1
        return memo[(n, x)]


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

    print(func(N, X))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N, X = map( int, input().split())
now = "P"
A = [1]*(N+1)
P = [1]*(N+1)
for i in range(N):
    A[i+1] = 2*A[i]+3
    P[i+1] = 2*P[i]+1
now = N
ans = 0
X -= 1
while now > 0:
    if A[now]//2 == X:
        ans += P[now-1]+1
        X = -1
        break
    elif A[now]//2 < X:
        ans += P[now-1]+1
        X -= A[now-1]+2
    else:
        X -= 1
    if X < 0:
        break
    now -= 1
if X == 0:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
B = [0] * (N + 1)
P = [1] * (N + 1)
for i in range(N):
  B[i + 1] = 2 * B[i] + 2
  P[i + 1] = 2 * P[i] + 1
S = [B[i] + P[i] for i in range(N + 1)]
cnt = 0
def burg(L, X):
  cnt = 0
  if L == 0:
    return 1
  elif X <= L:
    return 0
  elif X <= S[L - 1] + 1:
    return burg(L - 1, X - 1)
  else:
    return P[L - 1] + 1 + burg(L - 1, X - S[L - 1] - 2)
print(burg(N, X))

Submission status: Wrong Answer

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


def count_patties(l, x):
    if x <= 1:
        return 0
    if x >= layers[l]:
        return patties[l]
    y = layers[l-1]
    if x <= y+1:
        return count_patties(l-1, max(x-1, 0))
    else:
        return patties[l-1] + 1 + count_patties(l-1, x-(y+2))
    count_patties(l-1, max(x-y-1))


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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
a=[2**(i+2)-3 for i in range(N+1)]
p=[2**(i+1)-1 for i in range(N+1)]
def ans(n,x):
    if x<=1:
        return 0
    elif x<=2**(n+1)-2:
        return ans(n-1,x-1)
    elif x==2**(n+1)-1:
        return p[n-1]+1
    elif x<=2**(n+2)-4:
        return p[n-1]+1+ans(n-1,x+1-2**(n+1))
    else:
        return p[n]
print(ans(N,X))

Submission status: Wrong Answer

Solution code:

L=[];
P=[];

def dfs(n,x):
    if(n==0):
        return 1;
    if(x==1):
        return 0;
    if(x>=L[n]-2):
        return P[n];
    nx=x-1;
    if(nx<=L[n-1]):
        return dfs(n-1,nx);
    if(nx==L[n-1]+1):
        return P[n-1]+1;
    if(nx>L[n-1]+1):
        return P[n-1]+1+dfs(n-1,nx-(L[n-1]+1));
    
def main():
    N,X = input().split();
    n=int(N);
    x=int(X);
    for i in range(0,51):
        L.append(0);
        P.append(0);
    L[0]=1;
    P[0]=1;
    for i in range(1,n+1):
        L[i]=L[i-1]*2+3;
        P[i]=P[i-1]*2+1;
    print(dfs(n,x));
    
main();

Submission status: Wrong Answer

Solution code:

def p_(l):
    if l==0:
        return 1;
    return 1+2*p_(l-1)
def len_(l):
    if l==0:
        return 1;
    return 3+2*len_(l-1)
def solve(l,s):
    if s==0:
        return 0
    if s>=2+le[l-1]:
        return 1+p[l-1]+solve(l-1,s-2-le[l-1])
    elif s>=1+le[l-1]:
        return p[l-1]+solve(l-1,s-2-le[l-1])
    elif s>=2:
        return solve(l-1,s-1)
    return 0

n,x=map(int,input().split())
p=[0]*(n+1)
le=[0]*(n+1)
for i in range(1,n+1):
    p[i]=p_(i)
    le[i]=len_(i)
print(solve(n,x))

Submission status: Wrong Answer

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

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


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

def dfs(level,dist):
	ans = 0
	if level!=0 & dist==1:
		return 0
	elif dist==l[level]:
		return p[level]
	elif level==0:
		return 1
	elif dist==2+l[level-1]:
		return p[level-1]+1
	else:
		if dist <= 1+l[level-1]:
			ans = dfs(level-1,dist-1)
		else:
			ans = p[level-1]+1+dfs(level-1,dist-2-l[level-1])
	return ans

print(dfs(N,K))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq 
from itertools import *
import math
import random
import re
import string
import sys

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

all_elements = [1]
ps = [1]
bs = [0]
for i in range(50):
    all_elements.append(all_elements[-1] * 2 + 3)
    ps.append(ps[-1] * 2 + 1)
    bs.append(bs[-1] * 2 + 2)

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

    if x <= 1:
        return 0

    curr_elements = all_elements[n]
    prev_elements = all_elements[n - 1]

    if x <= prev_elements + 1:
        return from_bottom(n - 1, x - 1)
    if x == prev_elements + 1:
        return from_bottom(n - 1, x - 2) + 1
    if x <= prev_elements * 2 + 2:
        return 1 + ps[n - 1] + from_bottom(n - 1, x - 2 - prev_elements)
    if x == curr_elements:
        return 1 + 2 * bs[n - 1]

print(from_bottom(N, X))

Submission status: Wrong Answer

Solution code:
n,x = (int(i) for i in input().split())
def pc(n,k):
	if k==1: return 0
	elif k<2**(n+1)-1: return pc(n-1,k-1)
	elif k==2**(n+1)-1: return 2**n
	elif k<2**(n+2)-3: return 2**n+pc(n-1,k-2**(n+1)+1)
	else: return 2**(n+1)-1
print(pc(n,x))

Submission status: Wrong Answer

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

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


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


def dfs(level,dist):
	ans = 0
	if dist==1:
		return 0
	elif dist==l[level]:
		return p[level]
	elif level==0:
		return 1
	elif dist==2+l[level-1]:
		return p[level-1]+1
	else:
		if dist <= 1+l[level-1]:
			ans = dfs(level-1,dist-1)
		else:
			ans = p[level-1]+1+dfs(level-1,dist-2-l[level-1])
	return ans

print(dfs(N,K))

Submission status: Wrong Answer

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

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

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

print(ct(N, X))

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
def burgerLength(n):
    return(pow(2,n+2)-3)
def allpatNum(level):
    return(pow(2,level+1)-1)
def pat(level,x):
    L = burgerLength(level-1)
    if x == 1:
        ans = 0
    elif x <= 1 + L:
        ans = pat(level-1,x-1)
    elif x == 2 + L:
        ans = allpatNum(level-1) + 1
    elif x < 2 + L + L:
        ans = allpatNum(level-1) + 1 + pat(level-1,x-(2+L))
    else:
        ans = allpatNum(level)
    return(ans)
print(pat(N,X))

Submission status: Wrong Answer

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

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

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

print(ct(N, X))

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
ans = 0
def search(level, i):
	global ans
	if level == 0:
		return 1
	if i == 1:
		return ans
	elif i == 2 ** (level + 2) - 3:
		return ans + 2 ** (level + 1) - 1
	elif i == 2 ** (level + 1) - 1:
		return ans + 2 ** level
	elif i < 2 ** (level + 1) - 1:
		return search(level-1, i-1)
	else:
		ans += 2 ** level
		return search(level-1, i - (2 ** (level + 1) - 1))
print(search(n, x))

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
ans = 0
def search(level, i):
	global ans
	if i == 1:
		return ans
	elif i == 2 ** (level + 2) - 3:
		return ans + 2 ** (level + 1) - 1
	elif i == 2 ** (level + 1) - 1:
		return ans + 2 ** level
	elif i < 2 ** (level + 1) - 1:
		return search(level-1, i-1)
	else:
		ans += 2 ** level
		return search(level-1, i - (2 ** (level + 1) - 1))
print(search(n, x))

Submission status: Time Limit Exceeded

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

for _ in range(n):
    s = "b" + s + "p" + s + "b"

ans = s[:x].count("p")

print(ans)

Submission status: Time Limit Exceeded

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

def f(burger, counter):
    if counter == 0:
        return "P"

    L = f(burger, counter - 1)
    newBurger = "B" + L + "P" + L + "B"

    return newBurger

burger = f("", N)

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

Submission status: Time Limit Exceeded

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

B=[-1]*(N+1)

def make_buger(n):
  if n==0:
    return "P"
  elif B[n]!=-1:
    return B[n]
  else:
    if B[n-1]==-1:
      tmp=make_buger(n-1)
      B[n-1]=tmp
    else:
      tmp=B[n-1]
    tmp="B"+tmp+"P"+tmp+"B"
    B[n]=tmp
    return tmp
buger=make_buger(N)
print(buger[-X:].count("P"))

Submission status: Time Limit Exceeded

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

B=[-1]*(N+1)

def make_buger(n):
  if n==0:
    return "P"
  else:
    if B[n-1]==-1:
      tmp=make_buger(n-1)
      B[n-1]=tmp
    else:
      tmp=B[n-1]
    tmp="B"+tmp+"P"+tmp+"B"
    B[n]=tmp
    return tmp
buger=make_buger(N)
print(buger[-X:].count("P"))

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
hamburger_dict = {
  0: 'p'
}

def hamburger(n):
  if hamburger_dict.get(n):
    return hamburger_dict.get(n)
  return 'b' + hamburger(n - 1) + 'p' + hamburger(n - 1) + 'b'

print(hamburger(n)[0:x].count('p'))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

before_burger_P_index = list()
before_burger_P_index.append(1)
before_burger_thickness = 1

for i in range(1,N+1):
    #レベル L バーガー (L≥1) とは、
    #A : バン 1 枚、
    #B : レベル L−1 バーガー、
    #C : パティ 1 枚、
    #D : レベル L−1 バーガー、
    #E : バン 1 枚、をこの順に下から積み重ねたものである。
    
    new_burger_P_index = list()
    break_flag = False
    
    #A 処理不要
    #B 
    for P in before_burger_P_index:
        if P <= X:
            new_burger_P_index.append(P+1)
        else:
            break_flag = True
            break
            
    #C
    if not break_flag:
        new_burger_P_index.append(1+before_burger_thickness+1)
        
    #D
    if not break_flag:
        base = 1 + before_burger_thickness + 1
        
        for P in before_burger_P_index:
            if base + P <= X:
                new_burger_P_index.append(base + P)
            else:
                break_flag = True
                break
                
    #E 処理不要
    
    before_burger_P_index = new_burger_P_index
    before_burger_thickness = 3 + before_burger_thickness*2
    
    #print(i,before_burger_thickness,before_burger_P_index)
    
#print(before_burger_P_index)
print(bisect.bisect_right(before_burger_P_index,X))

#50レベルで4503599627370493 ≒ 4 * 10**15 層になる
#∴層を記載するとTLEする

Submission status: Time Limit Exceeded

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

def barger(n):
    if n == 0:
        return "P"
    else:
        return "B" + barger(n-1) + "P" + barger(n-1) + "B"

b = barger(n)[-x:].count("P")
print(b)

Submission status: Time Limit Exceeded

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

def make_burgur(l):
    if l == 0:
        burgur = 'P'
        return burgur
    if l >= 1:
        burgur='B'
        burgur += make_burgur(l-1)
        burgur += 'P'
        burgur += make_burgur(l-1)
        burgur += 'B'
        return burgur

burgur_x=make_burgur(n)[0:x]

print(burgur_x.count('P'))

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(100000)

N, X = in_nn()

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

dp = dict()


def count(L, X):

    if L == 0:
        return 1

    if X == 1:
        return 0

    global dp
    if (L, X) in dp:
        return dp[(L, X)]

    ret = 0
    if X <= blen[L] // 2:
        ret += count(L - 1, X - 1)
    else:
        ret += count(L - 1, blen[L - 1]) + 1
        if X > blen[L] // 2 + 1:
            X -= blen[L] // 2 + 1
            X = min(X, blen[L - 1])
            ret += count(L - 1, X)

    dp[(L, X)] = ret
    return ret


def main():

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def level(L):
  handburg = ""
  if L == 0:
    handburg = "P"
  else:
    handburg = "B"+level(L-1)+"P"+level(L-1)+"B"
  return handburg
N,X = map(int,input().split())
burger=level(N)
X=len(burger)-X
cnt = 0
for i in range(X,len(burger)):
  if burger[i] == 'P':
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,x = map(int,input().split())
L = 'P'
for i in range(n):
	L = 'B'+L+'P'+L+'B'
ans = 0
for i in range(x):
	if L[i] == 'P':
		ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,x = map(int,input().split())
cnt = 0
while n > 0 or x > 0:
    if x >= 2**(n+1)-1:
        cnt += 2**n
        x -= (2**(n+1)-1)
    else:
        x -= 1
    n -= 1
if x >= 1:
    cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#dpでできないかな？
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

a,x=MI()
size=[0 for i in range(a+1)]
size[0]=1
for i in range(a):
    size[i+1]=size[i]*2+3
#print(size)
#print(size[1])
def porb(k,n):
    if k==1 and n==0:
        return "p"
    elif k==size[n] or k==1:
        return "b"
    elif k>(size[n]+1)//2:
        return porb(k-(size[n]+1)//2,n-1)
    elif k==(size[n]+1)//2:
        return "p"
    else:
        return porb(k-1,n-1)
ans=0
#print(porb(x,a))
for i in range(1,x+1):
    #print(i)
    #print(porb(i,a))
    if porb(i,a)=="p":
        ans+=1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Mon Apr 27 21:30:42 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

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

n = N
eat = X

def dfs(x):
    x

ans = 0
#print(ans,eat,n)
while eat > 0:
    if eat == (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat = 0
        n -= 1
    elif eat > (pow(2,n+2) - 3 + 1) //2:
        ans += pow(2,n) - 1 + 1
        eat -= (pow(2,n+2) - 2) //2
        n -= 1
    else:
        eat -= 1
        n -= 1
#    print(ans,eat,n)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import deque
N, X = map(int, input().split())

d = deque()
current = "P"

for _ in range(1, N+1):
  d.appendleft("B")
  d.extend(current)
  d.append("P")
  d.extend(current)
  d.append("B")
  current = d

l = list(itertools.islice(d, len(d) - X, len(d)))
print(l.count("P"))

Submission status: Time Limit Exceeded

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

def eat(s):
    cnt=0
    for i in range(x):
        if s[i]=="P":
            cnt+=1
    return cnt

def dfs(i,bagar):
    #print(i,bagar)
    if i==n:
        return eat(bagar)
    return dfs(i+1,"B"+bagar+"P"+bagar+"B")

print(dfs(0,"P"))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

n, x = map(int, input().split())
ans = []

p = [1]
b = [0]

def cook(n):
	if n == 0:
		return p
	else:
		return b + cook(n-1) + p + cook(n-1) + b

ans = cook(n)
print(sum(ans[0:x]))

Submission status: Time Limit Exceeded

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


def dfs(level, idx, cnt_p):
    if X == idx+1:
        return 0
    elif X < 2**(level+1)-3+2:
        return cnt_p + dfs(level-1, idx+1, cnt_p)
    elif X == 2**(level+1)-3+2:
        return 2**(level)-1 + 1
    else:
        return cnt_p + 2**(level)-1 + 1 + dfs(level-1, idx+2**(level+1)-2, cnt_p)


ans = dfs(N, 0, 0)
print(ans)

Submission status: Time Limit Exceeded

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

def func(n):
    if n == 1:
        return [1, 3, 1]
    else:
        temp=func(n-1)
        return  [temp[0] + 1] + temp[1:] + [1] +\
                temp[:-1] + [temp[-1] + 1]

bg = func(N)
#print(bg)
cumulative = [0]
for i in range(len(bg)):
    cumulative.append(cumulative[i] + bg[i])
#print(cumulative)

#do binary search
left, right = -1, len(bg)

while right - left > 1:
    mid = (left + right) // 2
    if cumulative[mid] < X:
        left = mid
    else:
        right = mid


#print(right)
if right % 2 == 1: #in B
    print(sum([bg[i] for i in range(1, right, 2)]))
else:
    print(X - sum([bg[i] for i in range(0, right, 2)]))

Submission status: Time Limit Exceeded

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

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

a = burger(n-1)
b = a[:x]
print(b.count("P"))

Submission status: Time Limit Exceeded

Solution code:
n, x = map(int, input().split())
a = [0, 1, 1, 1, 0]
for _ in range(n-1):
    a = [0] + a + [1] + a + [0]
print(sum(a[:x]))

Submission status: Time Limit Exceeded

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

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

border = 2
nborder = 0
eaten = n
cnt = 1
ans = 0
after1 = 1
after3 = 2

while x > eaten:
    if cnt == border:
        if nborder == n-1: break
        eaten += nborder
        nborder += 1
        border = border*2 + 2
        after1 = nborder
    elif (cnt-1) % 4 == 0:
        ans += min(x-eaten,3)
        eaten += 3
    elif (cnt-1) % 4 == 1:
        eaten += after3
        after1 = after3
    elif (cnt-1) % 4 == 2:
        ans += 1
        eaten += 1
    elif (cnt-1) % 4 == 3:
        eaten += after1
        after3 = after1

    cnt += 1


print(ans)