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: Runtime Error

Solution code:
def main():

    """ convenient functions
    # for i, a in enumerate(iterable)
    # q, mod = divmod(a, b)
    # divmod(x, y) returns the tuple (x//y, x%y)
    # Higher-order function: reduce(operator.mul, xyz_count, 1)
    # manage median(s) using two heapq https://atcoder.jp/contests/abc127/tasks/abc127_f
    """

    """convenient decorator
    # @functools.lru_cache():
    # to facilitate use of recursive function
        # ex:
        # from functools import lru_cache
        # import sys
        # sys.setrecursionlimit(10**9)
        # @lru_cache(maxsize=None)
        # def fib(n):
        #     if n < 2:
        #         return n
        #     return fib(n-1) + fib(n-2)
        # print(fib(1000))
    """
    
    # import numpy as np
    import sys
    sys.setrecursionlimit(10**7)
    from itertools import accumulate, combinations, permutations, product # https://docs.python.org/ja/3/library/itertools.html
    # accumulate() returns iterator! to get list: list(accumulate())
    from math import factorial, ceil, floor, sqrt
    def factorize(n):
        """return the factors of the Arg and count of each factor
        
        Args:
            n (long): number to be resolved into factors
        
        Returns:
            list of tuples: factorize(220) returns [(2, 2), (5, 1), (11, 1)]
        """
        fct = []  # prime factor
        b, e = 2, 0  # base, exponent
        while b * b <= n:
            while n % b == 0:
                n = n // b
                e = e + 1
            if e > 0:
                fct.append((b, e))
            b, e = b + 1, 0
        if n > 1:
            fct.append((n, 1))
        return fct
    def combinations_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        # TODO: How should I do when n - r is negative?
        if n < 0 or r < 0:
            raise Exception('combinations_count(n, r) not defined when n or r is negative')
        if n - r < r: r = n - r
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]
        for p in range(2,r+1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p-1,r,p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot
        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
        return result
    def combinations_with_replacement_count(n, r):
        """Return the number of selecting r pieces of items from n kinds of items allowing individual elements to be repeated more than once.
        
        Args:
            n (long): number
            r (long): number
        
        Raises:
            Exception: not defined when n or r is negative
        
        Returns:
            long: number
        """
        if n < 0 or r < 0:
            raise Exception('combinations_with_replacement_count(n, r) not defined when n or r is negative')
        elif n == 0:
            return 1
        else:
            return combinations_count(n + r - 1, r)
    from bisect import bisect_left, bisect_right
    from collections import deque, Counter, defaultdict # https://docs.python.org/ja/3/library/collections.html#collections.deque
    from heapq import heapify, heappop, heappush, heappushpop, heapreplace,nlargest,nsmallest # https://docs.python.org/ja/3/library/heapq.html
    from copy import deepcopy, copy # https://docs.python.org/ja/3/library/copy.html
    import operator
    from operator import itemgetter #sort 
    # ex1: List.sort(key=itemgetter(1))
    # ex2: sorted(tuples, key=itemgetter(1,2))
    from functools import reduce, lru_cache
    def chmin(x, y):
        """change minimum
        if x > y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current minimum value
            y (long): potential minimum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x > y:
            x = y
            return (x, True)
        else:
            return (x, False)
    def chmax(x, y):
        """change maximum
        if x < y, x = y and return (x, True).
        convenient when solving problems of dp[i]
        
        Args:
            x (long): current maximum value
            y (long): potential maximum value
        
        Returns:
            (x, bool): (x, True) when updated, else (x, False)
        """
        if x < y:
            x = y
            return (x, True)
        else:
            return (x, False)

    from fractions import gcd # Deprecated since version 3.5: Use math.gcd() instead.
    def gcds(numbers):
        return reduce(gcd, numbers)
    def lcm(x, y):
        return (x * y) // gcd(x, y)
    def lcms(numbers):
        return reduce(lcm, numbers, 1)

    # first create factorial_list
    # fac_list = mod_factorial_list(n)
    INF = 10 ** 18
    MOD = 10 ** 9 + 7
    modpow = lambda a, n, p = MOD: pow(a, n, p) # Recursive function in python is slow!
    def modinv(a, p = MOD):
        # evaluate reciprocal using Fermat's little theorem:
        # a**(p-1) is identical to 1 (mod p) when a and p is coprime
        return modpow(a, p-2, p)
    def modinv_list(n, p = MOD):
        if n <= 1:
            return [0,1][:n+1]
        else:
            inv_t = [0,1]
            for i in range(2, n+1):
                inv_t += [inv_t[p % i] * (p - int(p / i)) % p]
            return inv_t
    def modfactorial_list(n, p = MOD):
        if n == 0:
            return [1]
        else:
            l = [0] * (n+1)
            tmp = 1
            for i in range(1, n+1):
                tmp = tmp * i % p
                l[i] = tmp
            return l
    def modcomb(n, k, fac_list = [], p = MOD):
        # fac_list = modfactorial_list(100)
        # print(modcomb(100, 5, modfactorial_list(100)))
        from math import factorial
        if n < 0 or k < 0 or n < k: return 0
        if n == 0 or k == 0: return 1
        if len(fac_list) <= n:
            a = factorial(n) % p
            b = factorial(k) % p
            c = factorial(n-k) % p
        else:
            a = fac_list[n]
            b = fac_list[k]
            c = fac_list[n-k]
        return (a * modpow(b, p-2, p) * modpow(c, p-2, p)) % p
    def modadd(a, b, p = MOD):
        return (a + b) % MOD
    def modsub(a, b, p = MOD):
        return (a - b) % p
    def modmul(a, b, p = MOD):
        return ((a % p) * (b % p)) % p
    def moddiv(a, b, p = MOD):
        return modmul(a, modpow(b, p-2, p))

    class UnionFindTree:
        """union find tree class
        TODO: fix this description...
        how to use (example):
        >>  uf = UnionFindTree(N) 
        >>  if uf.find_root(a) == uf.find_root(b):
        >>      do something
        >>  else:
        >>      do something
        >>      uf.unite(a, b)
        """
        def __init__(self, N):
            self.root = [-1] * (N+1)
            self.rank   = [0]  * (N+1)
            self.connected_num = [1] * (N+1)
    
        def find_root(self,x):
            root = self.root
            while root[x] != -1:
                x = root[x]
            return x
    
        def unite(self,x,y):
            root = self.root
            rank = self.rank
            connected_num = self.connected_num
            find_root = self.find_root
    
            rx = find_root(x)
            ry = find_root(y)
            if rx != ry:
                if rank[rx] < rank[ry]:
                    root[rx] = ry
                    rx,ry = ry,rx
                else:
                    if rank[rx] == rank[ry]:
                        rank[rx] += 1
                    root[ry] = rx       
                connected_num[rx] += connected_num[ry]

    """ initialize variables and set inputs
    # initialize variables
        # to initialize list, use [0] * n
        # to initialize two dimentional array, use [[0] * N for _ in range(N)]
    # set inputs
        # put inputs between specific values (almost as quickly)
        # ex) S = [-INF] + [int(r()) for _ in range(A)] + [INF]
        # open(0).read() is sometimes useful:
        # ex) n, m, *x = map(int, open(0).read().split())
        #     min(x[::2]) - max(x[1::2])
        # ex2) *x, = map(int, open(0).read().split())
        #     don't forget to add comma after *x if only one variable is used
    # preprocessing
        # transpose = [x for x in zip(*data)]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
        # flat = [flatten for inner in data for flatten in inner]
        # ex) [[1, 2, 3], [4, 5, 6], [7, 8, 9]] => [1, 2, 3, 4, 5, 6, 7, 8, 9]
    # calculate and output
        # output pattern
        # ex1) print(*l) => when l = [2, 5, 6], printed 2 5 6
    """

    # functions used
    r = lambda: sys.stdin.readline().strip()
    r_int = lambda: int(r())
    R = lambda: list(map(int, r().split()))
    Rmap = lambda: map(int, r().split())
    Rfloat = lambda: list(map(float, r().split()))
    Rtuple = lambda: tuple(map(int, r().split()))

    """ how to treat input
    # single int: int(r())
    # single string: r()
    # single float: float(r())
    # line int: R()
    # line string: r().split()
    # line (str, int, int): [j if i == 0 else int(j) for i, j in enumerate(r().split())]
    # lines int: [R() for _ in range(n)]
    """

    if __name__ != '__main__':
        # for test
        sys.stdin = open('sample.txt')
        
    # ----------------------------------
    # main

    N, X = R()
    @lru_cache(maxsize=None)
    def burger(l):
        if l == 0:
            return 'P'
        else:
            return 'B' + burger(l-1) + 'P' + burger(l-1) + 'B'
    print(burger(N)[-X:].count('P'))
    # end of main
    # ----------------------------------

    """memo: how to use defaultdict of list
    # initialize
    Dic = defaultdict(list)
    # append / extend
    Dic[x].append(y)
    # three methods for loop: keys(), values(), items()
    for k, v in Dic.items():
    """
    
    """memo: how to solve binary problems
    # to make binary digits text
    >>> a = 5
    >>> bin_str_a = format(a, '#06b')
    >>> print(bin_str_a)
    0b0101 # first 2 strings (='0b') indicates it is binary
    """
    
    """memo: how to solve the problem
    creating simple test/answer
    greed
    simple dp
    graph
    """

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def eat(L,X):
    if L == 0: return 1
    if X == 1: return 0
    elif X <= len_burger(L-1)+1: return eat(L-1,X-1)
    elif X == len_burger(L-1)+2: return num_ban(L-1)+1
    elif X < 2*len_burger(L-1)+3: return num_ban(L-1)+1+eat(L-1,X-len_burger(L-1)-2)
    elif X == len_burger(L): return num_ban(L)

def solve():
    N,X = [int(s) for s in input().split() if s]
    
    print(eat(N,X))

solve()

Submission status: Runtime Error

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

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

def calc(N, X): #レベルNバーガーの下からX層に含まれるパティの枚数
    if N == 0: #全てパティ
        if X == 0:
            return 0
        else:
            return 1
    if X == 1:
        return 0
    # print (N - 1)
    if 1 <= X <= a[N - 1]:
        # print ('A')
        return calc(N - 1, X - 1)
    if X == 2 + a[N - 1]:
        # print ('B')
        return p[N - 1] + 1
    if 2 +a[N - 1] < X <= 2 + 2 * a[N - 1]:
        # print ('C')
        return p[N - 1] + 1 + calc(N - 1, max(X - 2 - a[N - 1]), 0)
    if X == 3 + 2 * 2 * a[N - 1]:
        # print ('D')
        return 2 * p[N - 1] + 1

print (calc(N, X))

Submission status: Runtime Error

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

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

def calc(N, X): #レベルNバーガーの下からX層に含まれるパティの枚数
    if N == 0: #全てパティ
        if X == 0:
            return 0
        else:
            return 1
    if X == 1:
        return 0
    # print (N - 1)
    if 1 <= X <= a[N - 1]:
        # print ('A')
        return calc(N - 1, X - 1)
    if X == 2 + a[N - 1]:
        # print ('B')
        return p[N - 1] + 1
    if 2 +a[N - 1] < X <= 2 + 2 * a[N - 1]:
        # print ('C')
        return p[N - 1] + 1 + calc(N - 1, X - 2 - a[N - 1])
    if X == 3 + 2 * 2 * a[N - 1]:
        # print ('D')
        return 2 * p[N - 1] + 1

print (calc(N, X))

Submission status: Runtime Error

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

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

print (len(a))
def calc(N, X): #レベルNバーガーの下からX層に含まれるパティの枚数
    if N == 0: #全てパティ
        if X == 0:
            return 0
        else:
            return 1
    if X == 1:
        return 0
    # print (N - 1)
    if 1 <= X <= a[N - 1]:
        # print ('A')
        return calc(N - 1, X - 1)
    if X == 2 + a[N - 1]:
        # print ('B')
        return p[N - 1] + 1
    if 2 +a[N - 1] < X <= 2 + 2 * a[N - 1]:
        # print ('C')
        return p[N - 1] + 1 + calc(N - 1, X - 2 - a[N - 1])
    if X == 3 + 2 * 2 * a[N - 1]:
        # print ('D')
        return 2 * p[N - 1] + 1

print (calc(N, X))

Submission status: Runtime Error

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

lst = ['A'] * (N + 1)
def burger(s): #レベルsバーガーを返す
    if lst[s] != 'A':
        return lst[s]
    if s == 0:
        lst[s] = 'P'
        return lst[s]
    else:
        lst[s] = str('B' + burger(s-1) + 'P' + burger(s-1) + 'B')
        return lst[s]

s = burger(N)

count = 0
for i in range(X):
    if lst[N][i] == 'P':
        count += 1

print (count)

Submission status: Runtime Error

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

lst = ['A'] * (N + 1)
def burger(s): #レベルsバーガーを返す
    if lst[s] != 'A':
        return lst[s]
    if s == 0:
        lst[s] = 'P'
        return lst[s]
    else:
        lst[s] = str('B' + burger(s-1) + 'P' + burger(s-1) + 'B')
        return lst[s]

s = burger(N)

count = 0
for i in range(X):
    if lst[N][i] == 'P':
        count += 1

print (count)

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
burger = []
for i in range(n+1):
    if i == 0:
        burger.append("p")
    else:
        burger.append("b" + burger[i-1] + "p" + burger[i-1] + "b")
s = str(burger[n])
layer = s[:x]
print(layer.count("p"))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
pre="P"
for i in range(1,n):
  cur="B"+pre+"P"+pre+"B"
  pre=cur
print(cur[:k].count("P"))

Submission status: Runtime Error

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

def create_barger(l):
    if l == 0:
        return "P"
    else:
        temp = create_barger(l-1)
        return "B" + temp + "P" + temp + "B"

barger = create_barger(n)
eat = barger[:x]
print(eat.count("P"))

Submission status: Runtime Error

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

def create_barger(l):
    if l == 0:
        return "P"
    else:
        temp = create_barger(l-1)
        return "B" + temp + "P" + temp + "B"

barger = create_barger(n)
ans = 0
print(barger)
for i in range(x):
    if barger[i] == "P":
        ans += 1
print(ans)

Submission status: Runtime Error

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


def make_memo(level):
    burgers = [''] * (N+1)
    def _make(level):
        if level == 0:
            return 'P'
        if burgers[level]  != '':
            return burgers[level]
        burgers[level] = 'B' + _make(level-1) + 'P' + _make(level-1) + 'B'
        return burgers[level]
    return _make(level)

burger = make_memo(N)
sum_p = 0
for i in range(X):
    if burger[i] == 'P':
        sum_p += 1
print(sum_p)

Submission status: Runtime Error

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

def keisan(n,x):
    if x <= 1:
        return 0
    elif 1 < x <= 2**(n+1) - 2:
        return keisan(n-1,x-1)
    elif x == 2**(n+1) - 1:
        return 2**n
    else:
        return 2**n + keisan(n-1,x-(2**(n+1)-1))

print(keisan(N,X))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)

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

if X < N :
    print(0)
else :
    burger = [-1] * (N + 1)
    def makeBurger(level) :
        if level == 0 :
            return '1'
        if burger[level] == -1 :
            middle = makeBurger(level - 1)
            burger[level - 1] = middle
        else :
            middle = burger[level - 1]
        return '0' + middle + '1' + middle + '0'
    ans = makeBurger(N)[:X]
    print(ans.count('1'))

Submission status: Runtime Error

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

if X < N :
    print(0)
else :
    burger = [-1] * (N + 1)
    def makeBurger(level) :
        if level == 0 :
            return '1'
        if burger[level] == -1 :
            middle = makeBurger(level - 1)
            burger[level - 1] = middle
        else :
            middle = burger[level - 1]
        return '0' + middle + '1' + middle + '0'
    ans = makeBurger(N)[:X]
    print(ans.count('1'))

Submission status: Runtime Error

Solution code:
n,k=map(int,input().split())
burger=[None]*n
burger[0]="P"
for i in range(1,n):
  burger[i]="B"+burger[i-1]+"P"+burger[i-1]+"B"
print(sum(1 for i in burger[-1][:k] if i=="P"))

Submission status: Runtime Error

Solution code:
def burger(l):
    if not l:
        return 'P'
    s = 'B' + burger(l - 1) + 'P' + burger(l - 1) + 'B'
    return s
s = ''
n = int(input())
print(burger(n).count('P'))

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, X = map(int, input().split())
l, p = [1], [1]

def f(N, X):
    for i in range(N):
        if N == 0:
            return 0 if X == 0 else 1
        elif X <= 1 + l[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: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

N, X = map(int, input().split())
l, p = [1], [1]

def f(N, X)
    for i in range(N):
        if N == 0:
            return 0 if X == 0 else 1
        elif X <= 1 + l[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: Runtime Error

Solution code:
# 誤読

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

layer = 1
for _ in range(N):
    layer = layer * 2 + 3

def calc(n, i, layer):
    if n == 1:
        return "BPPPB"[i-1]
    else:
        if i == layer // 2 + 1:
            return "P"
        
        if i > layer // 2:
            i = layer - i + 1
        
        return calc(n-1, i, (layer-3) // 2)

ans = calc(N, X, layer)
print(ans)

Submission status: Runtime Error

Solution code:
n,x = map(int,input().split())
barger = 'bpppb'
p_cnt = 0
cnt = 1
front_barger = 'b'
for N in range(n):
    barger = 'b' + barger + 'p' + barger + 'b'
for i in range(x + 1):
    if barger[i] == 'p':
        p_cnt += 1
print(p_cnt)

Submission status: Runtime Error

Solution code:
lst = [1]

def burger(lst : list[int]):
  bls = [0]
  bls.append(lst)
  bls.append(1)
  bls.append(lst)
  bls.append(0)
  
  return bls

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

for i in range(n):
  eat = burger(lst)

print(eat[:x])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



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

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

    return _f(N, X)


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
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



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

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

    return _f(N, X)


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
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N, X = [int(nx) for nx in input().split()]
L = "P"
for n in range(1, N+1):
  L = "B" + L + "P" + L + "B"
print(L[0:X].count("P"))

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

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

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

print(f(n,x))

Submission status: Runtime Error

Solution code:
# coding: utf-8

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

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

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

print(f(n,x))

Submission status: Runtime Error

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

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def dfs(N,X):
    if N == 0:
        return 0 
    elif X <= 1 + a[N-1]:
        return dfs(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 + dfs(N-1, X-2-a[N-1])
    else:
        2*p[N-1]+1
    
print(dfs(N,K))

Submission status: Runtime Error

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

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def dfs(N,X):
    if N == 0:
        return 0 
    elif X <= 1 + a[N-1]:
        return dfs(N-1, X-1)
    elif X == 2 + a[N-1]:
        return p[N-1]
    elif X <= 2 + 2*a[N-1]:
        return p[N-1] + 1 + dfs(N-1, X-2-a[N-1])
    else:
        2*p[N-1]+1
    
print(dfs(N,K))

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
import sys
sys.setrecursionlimit(10000000)
def dfs(cur):
    if cur == 0:
        return 'p'
    l_1 = dfs(cur-1)
    if len(l_1) >= K:
        l_1 = l_1[:K]
    barger = 'b' + l_1 + 'p' + l_1 + 'b'
    return barger
ans = dfs(N)[:K].count('p')
print(ans)

Submission status: Runtime Error

Solution code:
N,K = map(int,input().split())
def dfs(cur):
    if cur == 0:
        return 'p'
    l_1 = dfs(cur-1)
    barger = 'b' + l_1 + 'p' + l_1 + 'b'
    return barger
ans = dfs(N)[:K].count('p')
print(ans)

Submission status: Runtime Error

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

ans = 0

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


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

Submission status: Runtime Error

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

ans = 0

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


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

Submission status: Runtime Error

Solution code:
def level_l(l):
  burger = ''
  if l == 0:
    return 'P'
  else:
    burger = 'B' + level_l(l-1) + 'P' + level_l(l-1) + 'B'
    return burger
  
n, x = map(int, input().split())

level_n = level_l(n)
level_n += 'B'

level_N = []
count = 0
for i in range(len(level_n)-1):
  if level_n[i] == 'P':
    count += 1
  level_N.append(count)

print(level_N[-1]-level_N[-x-1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)

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

def burger(N):
  if N == 0:
    return 'P'
  else:
    subburger = burger(N-1)
    return 'B' + subburger + 'P' + subburger + 'B'
print(burger(N)[:X].count('P'))

Submission status: Runtime Error

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

def burger(N):
  if N == 0:
    return 'P'
  else:
    subburger = burger(N-1)
    return 'B' + subburger + 'P' + subburger + 'B'
print(burger(N)[:X+1].count('P'))

Submission status: Runtime Error

Solution code:
N, X = map(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:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= 1 + a[N - 1]:
        return f(N - 1, X - 1)
    else:
        return p[N - 1] + 1 + f(N - 1, X - 2 - a[N - 1])

print(f(N, X))

Submission status: Runtime Error

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


def f(n):
    # レベルnの総数
    if n == 0:
        return 1
    else:
        return 2 * f(n - 1) + 3


def g(n):
    # レベルnのpの数
    if n == 0:
        return 1
    else:
        return 2 * g(n - 1) + 1


def dfs(n, x):
    # 総数
    m = f(n)
    # 真ん中
    a = (m + 1) // 2

    if x == a:
        return g(n - 1) + 1
    elif x == 1:
        return 0
    elif x < a:
        return dfs(n - 1, x - 1)
    elif x >= a:
        return g(n - 1) + 1 + dfs(n - 1, x - a)
    elif x == m:
        return 2 * g(n - 1) + 1


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

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=["p"]
i=0
while len(l)<x:
  i+=1
  l=["b"]+l+["p"]+l+["b"]
for j in range(n-i):
  l=["b"]+l
c=0
for i in range(x):
  if l[i]=="p":
    c+=1
print(c)

Submission status: Runtime Error

Solution code:
from functools import lru_cache


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


@lru_cache(maxsize=None)
def burger(n: int):
    if n == 0:
        return "P"
    else:
        return "B" + burger(n-1) + "P" + burger(n-1) + "B"

b = burger(N)
b = b[:X]
c = [c for c in b if c == "P"]
print(len(c))

Submission status: Runtime Error

Solution code:
l=[1]
p=[1]
N,X=map(int,input().split())
for i in range(N):
    l.append(l[i]*2+3)
    p.append(p[i]*2+1)
def calc(n,x):
    if n==0 and x==1:
        return 1
    if x==0 or x==1:
        return 0
    if x<=l[n]//2:
        return calc(n-1,x-1)
    elif x==l[n]//2+1:
        return p[n-1]+1
    else:
        return p[n-1]+1+calc(n-1,x-(l[n-1]+2))

print(calc(N,X))

Submission status: Runtime Error

Solution code:

ans = 0
def count_ans(level, index, len_dic, p_dic):
    global ans
    if level == 0:
        ans += 1
    else:
        if index == 0:
            pass
        elif index == len_dic[level] // 2:
            ans += 1
            ans += p_dic[level - 1]
        elif index == len_dic[level] - 1:
            ans += p_dic[level]
        elif index > len_dic[level] // 2:
            ans += p_dic[level - 1] + 1
            index_next = index - len_dic[level - 1] - 2
            count_ans(level - 1, index_next, len_dic, p_dic)
        else:
            index_next = index - 1
            count_ans(level - 1, index_next, len_dic, p_dic)


def get_len_dic(level):
    len_dic = [1]
    for i in range(level):
        len_dic.append(len_dic[-1] * 2 + 3)
    return len_dic

def get_p_dic(level):
    p_dic = [1]
    for i in range(level - 1):
        p_dic.append(p_dic[-1] * 2 + 1)
    return p_dic

def main():
    global ans
    level, eat_num = map(int, input().split())
    len_dic = get_len_dic(level)
    p_dic = get_p_dic(level)
    count_ans(level, eat_num - 1, len_dic, p_dic)
    print(ans)


if __name__ == '__main__':
    main()