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:
n, x = map(int, input().split())

p = 'P'

def burger(n):
    if n == 0:
        return 'P'
    mn = burger(n-1)
    p = 'B' + mn + 'P' + mn + 'B'

    return str(p)


lb = burger(n)

eat = lb[ : x]
print(eat.count('P'))

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())
layers = [1]
pats = [1]
cnt = 1
p_cnt = 1
for _ in range(n):
  cnt = cnt * 2 + 3
  p_cnt = p_cnt * 2 + 1
  layers.append(cnt)
  pats.append(p_cnt)
def solve(lev, rest):
  if rest == 0:
    return 0
  if rest - 1 <= (layers[lev] - 3) // 2:
    return solve(lev - 1, rest - 1)
  elif rest - 1 == (layers[lev] - 3) // 2:
    return pats[lev - 1] + 1
  else:
    return pats[lev - 1] + 1 + solve(lev - 1, rest - 1 - layers[lev - 1] - 1)

print(solve(n, x))

Submission status: Runtime Error

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

result = 'P'

for i in range(1, N+1):
    result = 'B' + result + 'P' + result + 'B'
    if len(result) >= X:
        break
    
print(result[:X].count('P'))

Submission status: Runtime Error

Solution code:
def abc115_d():
    n, x = map(int, input().split())
    burger = "P"
    for i in range(n):
        burger = ("B" + burger + "P" + burger + "B")[:x]

    print(burger.count("P"))


abc115_d()

Submission status: Runtime Error

Solution code:
class Burg:
    def __init__(self):
        self.lv = [None] * 51
        self.lv[0] = 1
        # self.string = ''

    def make_burg(self, n):
        if n == 0:
            return 'P'
        else:
            if self.lv[n] is None:
                tmp = self.make_burg(n - 1)
                self.lv[n] = 'B' + tmp + 'P' + tmp + 'B'
            return self.lv[n]


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

gen = Burg()
string = gen.make_burg(n)
div = string[:x]
print(div.count('P'))

Submission status: Runtime Error

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

memo = {0:'p'}
def f(m):
    if m in memo:
        return memo[m]
    tmp =  'b' + f(m-1) + 'p' + f(m-1) + 'b'
    memo[m] = tmp
    return tmp

print(len([i for i in f(n)[:x] if i == 'p']))

Submission status: Runtime Error

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

result = 'P'

for i in range(1, N+1):
    result = 'B' + result + 'P' + result + 'B'
    
print(result[:X].count('P'))

Submission status: Runtime Error

Solution code:
n,x=[int(i) for i in input().split()]
A=["B","P","B"]
B=["P","P"]
for i in range(n):
    ans=A[0]+B[0]+A[1]+B[1]+A[2]
    B[0]=ans
    B[1]=ans
result=0
for i in range(x):
    if ans[i]=="P":
        result+=1
print(result)

Submission status: Runtime Error

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

result = ['P']

for i in range(1, N+1):
    result.append('B' + result[i-1] + 'P' + result[i-1] + 'B')
    
print(result[-1][:X].count('P'))

Submission status: Runtime Error

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
	else: return 2**n+pc(n-1,k-2**(n+1)+1)
print(pc(n,x))

Submission status: Runtime Error

Solution code:
def abc115_d():
    n, x = map(int, input().split())
    burgers = ["P"] * (n+1)
    for i in range(n):
        burgers[i+1] = "B" + burgers[i] + "P" + burgers[i] + "B"

    print(burgers[n][:x].count("P"))


abc115_d()

Submission status: Runtime Error

Solution code:
N,X = map(int, raw_input().split())
A = [0]*N
B = [0]*N
A[0] = 1
B[0] = 1
for i in range(1,N):
  A[i] = 2*A[i-1]+3
  B[i] = 2*B[i-1]+1

def f(N,X):
  if N==0:
    return 1
  if X<=1:
    return 0
  if X<=1+A[N-1]:
    return f(N-1, X-1)
  if X<=1+A[N-1]+1:
    return B[N-1]+1
  if X<=1+A[N-1]+1+A[N-1]:
    return B[N-1]+1+f(N-1, X-2-A[N-1])
  if X<=1+A[N-1]+1+A[N-1]<=1:
    return 2*B[N-1]+1
  print N,X

print f(N,X)

Submission status: Runtime Error

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

b = 'P'
for _ in range(N):
  b = 'B'+b+'P'+b+'B'

print(b[:X].count('P'))