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:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, X = MAP()

# a_0 = 1, p_0 = 1
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):
    if N == 0:
        if X <= 0:
            return 0
        if X == 0:
            return 1
    elif X <= a[N-1] + 1:
        return f(N-1, X-1)
    elif X > a[N-1] + 1:
        return p[N-1] + 1 + f(N-1, X - (a[N-1] + 1 + 1))

print(f(N, X))

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N,X = map(int, input().split())
burger = [1]*(N+1)
paty = [1]*(N+1)

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

ans = 0
while X>0:
    if N==0:
        ans += 1
        break

    if X<=(burger[N]//2):
        X -= 1
    elif X==(burger[N]//2+1):
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X<burger[N]:
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X==burger[N]:
        ans += paty[N]
        x -= burger[N]
    N -= 1

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N,X = map(int, input().split())
burger = [1]*(N+1)
paty = [1]*(N+1)

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

ans = 0
while X>0:
    if N==0:
        ans += 1
        break

    if X==1:
        X -= 1
    elif X<=(burger[N]/2):
        X -= 1
    elif X==(burger[N]/2+1):
        ans += paty[N-1]+1
        X -= (burger[N]/2+1)
    elif X<burger[N]:
        ans += paty[N-1]+1
        X -= (burger[N]/2+1)
    elif X==burger[N]:
        ans += paty[N]
        x -= burger[N]
    N -= 1

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N,X = map(int, input().split())
burger = [1]*(N+1)
paty = [1]*(N+1)

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

ans = 0
while X>0:
    if N==0:
        ans += 1
        break

    if X==1:
        X -= 1
    elif X<=(burger[N]//2):
        X -= 1
    elif X==(burger[N]//2+1):
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X<burger[N]:
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X==burger[N]:
        ans += paty[N]
        x -= burger[N]
    N -= 1

print(ans)

Submission status: Runtime Error

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
#from scipy.misc import comb

N,X = map(int, input().split())
burger = [1]*(N+1)
paty = [1]*(N+1)

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

ans = 0
while X>0:
    if X==1:
        X -= 1
    elif X<=(burger[N]//2):
        X -= 1
    elif X==(burger[N]//2+1):
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X<burger[N]:
        ans += paty[N-1]+1
        X -= (burger[N]//2+1)
    elif X==burger[N]:
        ans += paty[N]
        x -= burger[N]
    N -= 1

print(ans)

Submission status: Runtime Error

Solution code:
ri = lambda: map(int, input().split(' '))
L = [1]
C = [1]

def rec(n, x):
	if x <= 1:
		return 0

	if x == L[n]:
		return 2*C[L-1] + 1

	ans = 0
	if x >= L[n-1] + 2:
		ans += C[n-1] + 1
		ans += rec(n-1, x-L[n-1]-2)
	else:
		ans += rec(n-1, x-1)

	return ans

if __name__ == '__main__':
	N, X = ri()
	for i in range(1, N+1):
		L.append(2*L[i-1] + 3)
		C.append(2*C[i-1] + 1)
	ans = rec(N, X)
	print(ans)

Submission status: Runtime Error

Solution code:
import sys
L = [4 * (2 ** i) - 3 for i in range(51)]
P = [2 * (2 ** i) - 1 for i in range(51)]
N, X = map(int, input().split())
def solve(level, x):
  # print(level, x, file=sys.stderr)
  if x == 1:
    return 0
  elif x > L[level-1] + 2:
    return P[level-1] + 1 + solve(level-1, x - L[level-1] - 2)
  elif x == L[level-1] + 2:
    return solve(level-1, L[level-1] - 1) + 1
  else:
    return solve(level-1, x-1)
print(solve(N, X))

Submission status: Runtime Error

Solution code:
[N,X] = list(map(int,input().split(' ')))

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    elif x == 0:
      return 0
  elif int((2**(n+2)-3 - 1) / 2) >= x:
    return paty(n-1,x-2)
  elif int((2**(n+2)-3 + 1) / 2) == x:
    return paty(n-1,x-2) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -3)
  
ans = paty(N,X)
print(ans)

Submission status: Runtime Error

Solution code:
N, X = map(int, input().split())
dp = ["P"]
for i in range(N):
    dp.append("B" + dp[-1] + "P" + dp[-1] + "B")
print(sum([1 for i in dp[N][0:X] if i == "P"]))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,X = map(int,input().split())
burger_before = "P"
burger_after = ""

for i in range(1,N+1):
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    burger_before = burger_after

eat = burger_after[-X:]
#print(burger_after)
print(eat.count("P"))

Submission status: Runtime Error

Solution code:
def make_burger():
    global burger_before
    global burger_after
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    burger_before = burger_after    
    
N,X = map(int,input().split())
burger_before = "P"
burger_after = ""

for i in range(1,N+1):
    make_burger()

eat = burger_after[-X:]
#print(burger_after)
print(eat.count("P"))

Submission status: Runtime Error

Solution code:
def make_burger():
    global burger_before
    global burger_after
    #global burgerlist
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    append(burger_after)
    
N,X = map(int,input().split())
burgerlist = ["P"]
append = burgerlist.append

for i in range(1,N+1):
    burger_before = burgerlist[i-1]
    burger_after = ""
    make_burger()

eat = burgerlist[N][-X:]
print(burgerlist[N])
print(eat.count("P"))

Submission status: Runtime Error

Solution code:
def make_burger():
    global burger_before
    global burger_after
    #global burgerlist
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    append(burger_after)
    
N,X = map(int,input().split())
burgerlist = ["P"]
append = burgerlist.append

for i in range(1,N):
    burger_before = burgerlist[i-1]
    burger_after = ""
    make_burger()

eat = burgerlist[N-1][-X:]
print(eat.count("P"))

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
#N=3
#M=7

MEMO=[[0]*(2) for i in range(N+1)]
MEMO[0][0]=1
MEMO[0][1]=1

for i in range (1,N+1):
    MEMO[i][0]=MEMO[i-1][0]*2+3
    MEMO[i][1]=MEMO[i-1][1]*2+1
t=1
s=0
n=N-1
while(True):
        if(t==M):break
        if(t+MEMO[n][0]<M):
            if f==0:
                t=t+MEMO[n][0]+1
                s+=MEMO[n][1]+1
                f+=1
            else:
                s+=MEMO[n][1]
                break
        elif(t+MEMO[n][0]>M):
            t+=1
            n-=1
            f=0
        else:
            s+=MEMO[n][1]
            break
print(s)

Submission status: Runtime Error

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

a,p=[1],[1]

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

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

print(solve(N,X))

Submission status: Runtime Error

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

A = [1]
P = [1]
for i in range(n):
	A.append(A[i]*2+3)
	P.append(P[i]*2+1)
print(A,P)

def func(n,x):
	elif x == 1:
		return 0 if n != 0 else 1
	elif x <= 1+A[n-1]:
		return func(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+func(n-1,x-2-A[n-1])
	else:
		return 2*P[n-1]+1

print(func(n,x))

Submission status: Runtime Error

Solution code:
n,x=map(int,input().split())
ans="P"
for i in range(1,n+1):
	ans="B"+ans+"P"+ans+"B"
	if len(ans)>x:
		ans=ans[:x]
print(ans[:x].count("P"))

Submission status: Runtime Error

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

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

from functools import lru_cache
import sys

sys.setrecursionlimit(10*20)

@lru_cache(maxsize=None)
def count(N):
    if N == 0:
        return 1
    else:
        temp = pan(N-1)
        return 3 + 2 * count(N-1)
    
@lru_cache(maxsize=None)
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))

Submission status: Runtime Error

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

from functools import lru_cache
import sys

sys.setrecursionlimit(10*10)

@lru_cache(maxsize=None)
def count(N):
    if N == 0:
        return 1
    else:
        temp = pan(N-1)
        return 3 + 2 * count(N-1)
    
@lru_cache(maxsize=None)
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))

Submission status: Runtime Error

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

from functools import lru_cache

@lru_cache(maxsize=None)
def count(N):
    if N == 0:
        return 1
    else:
        temp = pan(N-1)
        return 3 + 2 * count(N-1)
    
@lru_cache(maxsize=None)
def calc(N,X):
    if N == 0:
        return 1
    center = count(N-1) + 1
    if X == 0 :
        return 0
    elif X < center:
        return calc(N-1,X-1)
    elif X == center:
        return calc(N-1,center-2) + 1
    elif X > center:
        return calc(N-1,X-center-1) + calc(N,center)
print(calc(N,X-1))

Submission status: Runtime Error

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 += patEaten(layer, toEat)
      toEat = 0
			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: Runtime Error

Solution code:
def getItemCount(L):
  if L == 0:
    return 1
  return 2*getItemCount(L-1) + 3
  
def getPatsCount(L, eaten):
  if eaten * 2 - 1 == getItemCount(L):
    return 2**(1+layer) + 1
  return 2**(1+layer)

def getAns(layer, eaten):
  items = getItemCount(layer)
  patsInLayer = getPatsCount(layer, eaten)
  if layer == 0 and eaten == 1:
    return 1
  if eaten == items:
    return patsInLayer
  elif eaten < items:
    return getAns(layer-1, eaten - 1)
  else:
    return patsInLayer + getAns(layer-1, eaten - 1)


layer, eaten = [int(x) for x in input().split()]
print(getAns(layer, eaten))

"""
tPats = 0
if layer != 0:
  while 1:
    items = getItemCount(layer)
    patsInLayer = getPatsCount(layer)

    if eaten == items:
      if layer != 0:
        tPats += patsInLayer
        eaten -= items
      break
    elif eaten < items:
      eaten -= 1
    elif eaten > items:
      tPats += patsInLayer + 1
      eaten -= items
    layer -= 1
    if layer < 0:
      break
else:
  if eaten == 1:
    print(1)
  else:
    print(0)
print(tPats)
"""

Submission status: Runtime Error

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

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

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

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):
    global ans
    # print(n ,x ,layer[n], patty[n], ans)
    if x == 0:
        print(ans)
        sys.exit()
    if layer[n] <= x:
        ans += patty[n]
        x -= layer[n]
        return x
    else:
        x -= 1
        x = eat(n-1, x)
        x -= 1
        ans += 1
        x = eat(n-1, x)
        x -= 1
x = eat(n, x)

Submission status: Runtime Error

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 pattiesCount(i) != p[i]:
#         raise Exception()
#     print(i, '->', pattiesCount(i), bunsCount(i), bothCount(i))

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


print(doit(n, eat))

Submission status: Runtime Error

Solution code:
n, x = map(int, input().split())
def doit(l, x):
    layers = 2 ** (l + 1) - 3
    if x >= layers + 2:
        return doit(l - 1, x - layers - 2) + 2 ** l
    elif x >= 1:
        return doit(l - 1, x - 1)
    else:
        return 0
print(doit(n, x))

Submission status: Runtime Error

Solution code:
inp = input().split()
layer = int(inp[0])
length = int(inp[1])
lengths = [5]
ps = [3]
for i in range(49):
  lengths.append(lengths[i]*2+3)
  ps.append(ps[i]*2+1)
print(stack(layer, length))

def stack(layer, length):
  if layer==1:
    return "BPPPB"[:length].count("P")
  else:
    if length==(lengths[layers-1]+1)/2:
      return ps[layers-1]+1
    elif length==(lengths[layers-1]+1)/2:
      return stack(layers-1, length-1)
    else:
      return ps[layers-1]+1+stack(layers-1, length-(lengths[layers-2]+2)

Submission status: Runtime Error

Solution code:
# D - Christmas

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

height = [1] # レベルnバーガーの高さ
for _ in range(N):
    height.append(height[-1]*2 + 3)

# dp[i][j]はレベルiバーガーの下j層に含まれるパティの数。ただしレベルiバーガーの高さの範囲外には-1を格納
dp = [[0]+[-1]*height[-1] for _ in range(N+1)] 
dp[0][1] = 1
    
for level in range(1,N+1):
    for n_from_bottom in range(1,height[-1]+1):
        if n_from_bottom > height[level]:
            break
        elif n_from_bottom == 2 * height[level-1] + 3:
            dp[level][n_from_bottom] = dp[level-1][height[level-1]] * 2 + 1
        elif n_from_bottom > height[level-1] + 2: 
            dp[level][n_from_bottom] = dp[level-1][height[level-1]] + 1 + dp[level-1][n_from_bottom - (height[level-1] + 2)]
        elif n_from_bottom == height[level-1] + 2: # 前のバーガー+底のバン+パティ
            dp[level][n_from_bottom] = dp[level-1][height[level-1]] + 1
        else:
            dp[level][n_from_bottom] = dp[level-1][n_from_bottom-1]
    
print(dp[N][X])

Submission status: Runtime Error

Solution code:
using System;
using System;
using System.Collections.Generic;
using System.Linq;


    class Solver5
    {
        /*
         * 
         * https://atcoder.jp/contests/abc115/tasks/abc115_d
         * 
         */
 public void Solve5()
        {
            var nx = u.readLongArrayBySplit();
			var n = nx[0];
            var x = nx[1];
            long ans = 0;

            while (true)
            {
                var thk = new long[5]{ 1, (long)Math.Pow(2,n + 1) - 3, 1, (long)Math.Pow(2, n + 1) - 3, 1 };
                var pc = new long[5] { 0, (long)Math.Pow(2, n ) - 1 , 1, (long)Math.Pow(2, n )- 1, 0 };
                for (int i = 0; i < 5; i++)
                {
                    if (x > thk[i])
                    {
                        x -= thk[i];
                        ans += pc[i];
                    }
                    else if (x < thk[i])
                    {
                        n--;
                        break;
                    }
                    else
                    {
                        ans += pc[i];
                        Console.WriteLine(ans.ToString());
                        return;
                    }
                }

            }

        }
        static void Main()
        {
            var solver = new Solver5();
            solver.Solve5();
        }
    }
    static class u
    {
      public static long[] readLongArrayBySplit() { return Console.ReadLine().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Solution code:
#include <bits/stdc++.h>
using namespace std;

int main() {
  long long int n, x, i;
  string result;
  cin >> n >> x;
  vector<string> burgers[51];
  burgers[0] = "P";
  burgers[1] = "BPPPB";
  burgers[2] = "BBPPPBPBPPPBB";
  i = 3;
  while (i<=50) {
    burgers[i] = "B" + burgers[i-1] + "P" + burgers[i-1] + "B";
    i+=1;
  }
  result = burgers[n][:x-1];
  cout << result;
  return 0;
}

/*
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<=50:
  burgers[i] = "B" + burgers[i-1] + "P" + burgers[i-1] + "B"
  i+=1
result = burgers[n][:x-1]
print(result.count("P"))
*/

Submission status: Runtime Error

Solution code:
n, x = (int(x) for x in input().split())
l = [0 for _ in range(x-n)]
if l == []: print(0)
else:
    print(l)
    for i in range(int(len(l)/6+1)):
        l[6*i] = 1
        l[6*i+1] = 1
        l[6*i+2] = 1
        l[6*i+4] = 1
    print(sum(l))

Submission status: Runtime Error

Solution code:
dp = ["" for i in range(51)]
dp[0] = "P"

def solve(n, dp):
    if n == 0:
        return dp[0]
    else:
        if dp[n] == "":
            k = solve(n - 1,dp)
            return 'B' + k + 'P' + k + 'B'
        else:
            return dp[n]
n, x = list(map(int, input().split()))
dp = solve(n,dp)
print(dp[-x:].count('P'))

Submission status: Runtime Error

Solution code:
T = [1]*(N + 1)
P = [1]*(N + 1)
for i in range(1, N+1):
	P[i] = P[i-1]*2 + 1
	T[i] = T[i-1]*2 + 3
def pate(n, x):
	if n == 0:
		if x > 0: return 1
		return 0
	mid = T[n]//2
	if x < mid:
		return pate(n-1, x-1)
	elif mid == x:
		return 1 + pate(n-1, x-2)
	else:
		return P[n-1] + 1 + pate(n-1, x-mid-1)

print(pate(N, X))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
N,X=map(int,input().split())

def dfs(count,object):
    count+=1
    object="B"+object+"P"+object+"B"
    if count<N:
        dfs(count,object)
    else:
        print(object)
        exit()

n=0
burger="P"

(dfs(n,burger))

Submission status: Runtime Error

Solution code:
n, x = map(int, (input().split()))
a, p = [1], [1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
#print("a = {}".format(a))
#print("p = {}".format(p))

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 == a[n-1]+2:
        return p[n-1]+1
    elif x <= 2*a[n-1]+3:
        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()))
a, p = [1], [1]
for i in range(n):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
print("a = {}".format(a))
print("p = {}".format(p))

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

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)

"""考え方
L0 : P
L1 : BPPPB
L2 : BBPPPBPBPPPBB
L3 : BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
L4 : ...

・レベルが1上がると、Pの数は2倍+1になる
・レベルが1上がると、総数は2倍+3になる


レベルiバーガーの厚さ（層の総数）をa_iとする
レベルiバーガーに含まれるパティの総数をp_iとする
「レベルNバーガーの下からX層に含まれるパティの枚数」をf(N,X)とする。

・N = 0のとき
f(0,X) = 1

・N >= 1のとき
f(N-1, Y)がわかると仮定すると、

(1) X = 1のとき、f(N,X) = 0 (一番下のバンだけ)

(2) 1 < X <= 1 + a_{i-1} のとき、f(N,X) = f(N-1, X-1)

i=2のとき、L2のときで
BBPPPB PBPPPBB
BPPPBB|ここまでのとき

(3) X = 2 + a_{i-1}のとき、f(N,X) = p_{i-1}+1
???


https://www.youtube.com/watch?v=1ONpCPN-IR8
"""
def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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


    def _dfs(depth, x):
        """ レベルdepthバーガーの、下からX層に含まれるパティの枚数を返す """
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[depth-1]:
            # 一番下のパン + その上のレベル N-1 バーガー + その上のパティ
            return _dfs(depth-1, x-1)
        else:
            # (前略) + その上のパティ + その上のレベル N-1 バーガーの下から x-2-As[depth-1]層
            return Ps[depth-1] + 1 + _dfs(depth-1, x-2-As[depth-1])

    ans = _dfs(N, X)

    print(ans)


def solve2():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


def solve3():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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

    # dp[i][x] := レベルiバーガーの下からx層に含まれているパティの総数
    dp = [[0]*(As[N]+1) for _ in range(N+1)]
    dp[0][0] = 0
    for i in range(1, As[N]+1):
        dp[0][i] = 1

    # 漸化式を解く
    for i in range(1, N+1):
        median = (As[i]+1)//2
        for x in range(X+1):
            if x < median:
                dp[i][x] = dp[i-1][x-1]
            elif x == median:
                dp[i][x] = Ps[i-1] + 1
            else:
                dp[i][x] = Ps[i-1] + 1 + dp[i-1][x-median]

    print(dp[N][X])



if __name__ == "__main__":
    solve3()

Submission status: Runtime Error

Solution code:
# -*- coding:utf-8 -*-
import sys
sys.setrecursionlimit(10000)

"""考え方
L0 : P
L1 : BPPPB
L2 : BBPPPBPBPPPBB
L3 : BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
L4 : ...

・レベルが1上がると、Pの数は2倍+1になる
・レベルが1上がると、総数は2倍+3になる


レベルiバーガーの厚さ（層の総数）をa_iとする
レベルiバーガーに含まれるパティの総数をp_iとする
「レベルNバーガーの下からX層に含まれるパティの枚数」をf(N,X)とする。

・N = 0のとき
f(0,X) = 1

・N >= 1のとき
f(N-1, Y)がわかると仮定すると、

(1) X = 1のとき、f(N,X) = 0 (一番下のバンだけ)

(2) 1 < X <= 1 + a_{i-1} のとき、f(N,X) = f(N-1, X-1)

i=2のとき、L2のときで
BBPPPB PBPPPBB
BPPPBB|ここまでのとき

(3) X = 2 + a_{i-1}のとき、f(N,X) = p_{i-1}+1
???


https://www.youtube.com/watch?v=1ONpCPN-IR8
"""
def solve():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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


    def _dfs(depth, x):
        """ レベルdepthバーガーの、下からX層に含まれるパティの枚数を返す """
        if depth == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + As[depth-1]:
            # 一番下のパン + その上のレベル N-1 バーガー + その上のパティ
            return _dfs(depth-1, x-1)
        else:
            # (前略) + その上のパティ + その上のレベル N-1 バーガーの下から x-2-As[depth-1]層
            return Ps[depth-1] + 1 + _dfs(depth-1, x-2-As[depth-1])

    ans = _dfs(N, X)

    print(ans)


def solve2():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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

    def f(n, x):
        """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
        if n == 0:
            return 0 if x <= 0 else 1

        median = (As[n]+1)//2

        if x < median:
            return f(n-1, x-1)
        elif x == median:
            return Ps[n-1] + 1
        elif x > median:
            return Ps[n-1] + 1 + f(n-1, x-median)

    ans = f(N, X)

    print(ans)


def solve3():
    N, X = list(map(int, sys.stdin.readline().split()))

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

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

    # dp[i][x] := レベルiバーガーの下からx層に含まれているパティの総数
    dp = [[0]*(As[N]+1) for _ in range(N+1)]
    dp[0][0] = 0
    dp[0][1] = 1

    for i in range(1, N+1):
        for x in range(X+1):
            median = (As[i]+1)//2
            if x < median:
                dp[i][x] = dp[i-1][x-1]
            elif x == median:
                dp[i][x] = Ps[i-1] + 1
            else:
                dp[i][x] = Ps[i-1] + 1 + dp[i-1][x-median]

    print(dp[N][X])



if __name__ == "__main__":
    solve3()