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: Accepted

Solution code:
N, X = [int(a) for a in input().split()]
ans = 0
now_level = N
num_list = [2 ** (n + 2) - 3 for n in range(N + 1)]
while X > 0:
    if X <= now_level:
        break
    num_list = [2 ** (n + 2) - 3 for n in range(now_level + 1)]
    plus_base = [a + now_level - b for a, b in zip(num_list, range(now_level + 1))]
    eat_num = max([a for a in plus_base if a <= X])
    eat_level = plus_base.index(eat_num)
    now_level = eat_level
    ans += int((num_list[eat_level] + 1) / 2 + 0.1)
    X -= eat_num
    if X > 0:
        X -= 1
        ans += 1
print(str(ans))

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

def alll(x):
    if not x:
        return 1
    return 3+2*alll(x-1)
def pate(n,x):
    if n == 0:
        return [0, 1][x == 1]
    result = 0
    if x == 0:
        return 0
    if x == alll(n):
        return 2**(n+1)-1
    if x == 2 + alll(n-1):
        return 2**n-1 + 1
    elif x > (alll(n)+1)//2:
        result += 2**n-1 + 1
        x -= (alll(n-1)+2)
    else:
        x -= 1
    return result + pate(n-1,x)      
N, X = inpl()
print(pate(N, X))

Submission status: Accepted

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

def func(n,k):
    if n==0:
        return 1
    a=2**(n+1)-1
    if k==a:
        return 2**n
    elif k==1:
        return 0
    elif k==2**(n+2)-3:
        return 2**(n+1)-1
    elif k<a:
        return func(n-1,k-1)
    else:
        return 2**n+func(n-1,k-(2**(n+1)-1))
print(func(N,X))

Submission status: Accepted

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: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

L = []
P = []

for i in range(N):
    if i == 0:
        L.append(1)
        P.append(1)
        continue
    else:
        L.append(L[i-1] * 2 + 3)
        P.append(P[i-1] * 2 + 1)

def g(k, x):
    if x == 0:
        return 0
    
    if k == 0:
        return 1
    
    if x < L[k-1] + 2:
        return g(k-1, x-1)
    
    if x == L[k-1] + 2:
        return P[k-1] + 1
    
    if x > L[k-1] + 2:
        return P[k-1] + 1 + g(k-1, x - (L[k-1] + 2))

print(g(N, X))

Submission status: Accepted

Solution code:
def levelup(X,N):
    if N==0 and X!=0:
        return 1
    if X==0:
        return 0
    elif X<2**(N+1)-1:
        return levelup(X-1,N-1)
    elif X<2**(N+2)-3:
        return 2**N - 1 + levelup(X-2**(N+1)+1,N-1) + 1
    elif X==2**(N+2)-3:
        return 2**(N+1) - 1

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

print(levelup(X,N))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
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 lev == 0:
    return 1
  if rest - 1 <= layers[lev - 1]:
    return solve(lev - 1, rest - 1)
  elif rest - 1 == layers[lev - 1]:
    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: Accepted

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

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

    if x <= 1:
        return 0
    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 ps[n]

def slow(n, x):
    burger = ['P']
    for i in range(n):
        burger = ['B'] + burger + ['P'] + burger + ['B'] 
    # print(burger)
    ans = 0
    for i in range(x):
        ans += burger[i] == 'P'
    return ans

# # debug
# while True:
#     for n in range(2, 50):
#         for x in range(6, all_elements[n]):
#             if from_bottom(n, x) != slow(n, x):
#                 print("error! n, x = ", n, x )
#                 print("wrong:", from_bottom(n, x))
#                 print("correct:", slow(n, x))
#                 sys.exit(0)

print(from_bottom(N, X))

Submission status: Accepted

Solution code:
def getN():
    return int(input())

def getMN():
    a = input().split()
    b = [int(i) for i in a]
    return b[0],b[1]

def getlist():
    a = input().split()
    b = [int(i) for i in a]
    return b

burger = [1] + [0 for i in range(50)]
niku = [1] + [0 for i in range(50)]
for i in range(50):
    burger[i+1] = 2 * burger[i] + 3
    niku[i+1] = 2 * niku[i] + 1

n, x = getMN()

def singleburger(x):
    if x <= 1:
        return 0
    elif x <= 4:
        return x-1
    else: return 3

def intonburger(n,x):
    if n == 1:
        return singleburger(x)
    if x <= 1:
        return 0
    elif x <= burger[n-1] + 1:
        return intonburger(n-1, x-1)
    elif x == burger[n-1] + 2:
        return niku[n-1] + 1
    elif x <= 2 * burger[n-1] + 2:
        return niku[n-1] + 1 + intonburger(n-1, x-burger[n-1]-2)
    else:
        return 2 * niku[n-1] + 1

print(intonburger(n,x))

Submission status: Accepted

Solution code:

L=[];
P=[];

def dfs(n,x):
    if(x==0):
        return 0;
    if(n==0):
        return 1;
    if(x==1):
        return 0;
    if(x>=L[n]-1):
        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: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,x = map(int, input().split())

d = [0 for _ in range(51)]
d[0] = 1
for i in range(50):
    d[i+1] = 3 + 2*d[i]

p = [0 for _ in range(51)]
p[0] = 1
for i in range(50):
    p[i+1] = 1 + 2*p[i]

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

    if 2+d[l-1]<=x:
        return f(l-1,d[l-1]) + 1 + f(l-1, x-1-d[l-1]-1)
    else:
        return f(l-1, x-1)

print(f(n,x))

Submission status: Accepted

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==le[l]:
        return p[l]
    elif 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(n+1):
    p[i]=p_(i)
    le[i]=len_(i)
print(solve(n,x))

Submission status: Accepted

Solution code:
import sys
import string
n = raw_input()
n,k = n.split(' ') 

l=[1]
f=[1]
for i in range(55):
    l.append(l[len(l)-1]*2+3)
    f.append(f[len(f)-1]*2+1)

def s(k,level):
    if (level==0):
        if (k>0): return 1
        return 0
    if (k==1): return 0
    if (k>=l[level]): return f[level]
    if (k<l[level]):
        if (k<=l[level-1]+1):
            return s(k-1,level-1)
        if (k==l[level-1]+2):
            return 1+s(k-1,level-1)
        return 1+f[level-1]+s(k-1-1-l[level-1],level-1)

n = string.atoi(n)
k = string.atoi(k)
print (s(k,n))

Submission status: Accepted

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

N, X = map(int, raw_input().split())
l = [0]*(N+1)
l[0]=1
p = [0]*(N+1)
p[0]=1
for i in range(1, N+1):
  l[i] = 2*l[i-1]+3
  p[i] = 2*p[i-1]+1
a = c(N,X)
print a

Submission status: Accepted

Solution code:
n,x = (int(i) for i in input().split())
def pc(n,k):
	if n and k==1: return 0
	elif k==1: return 1
	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: Accepted

Solution code:
n, x = map(int, input().split())
x -= 1
thick = [1]
for i in range(n):
    thick.append(thick[i] * 2 + 3)


def f(level, layer):
    if level == 0:
        return 1
    elif layer == 0:
        # print('start')
        return 0
    elif 1 <= layer <= thick[level-1]:
        # print('first')
        return f(level-1, layer-1)
    elif layer == thick[level-1]+1:
        # print('half')
        return f(level-1, thick[level-1]-1) + 1
    elif thick[level-1]+2 <= layer <= thick[level-1] * 2 + 1:
        # print('second')
        return f(level-1, thick[level-1]-1) + 1 + f(level-1, layer-thick[level-1]-2)
    elif layer == thick[level-1] * 2 + 2:
        # print('end')
        return f(level-1, thick[level-1]-1) * 2 + 1


print(f(n, x))

Submission status: Accepted

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:
		return 1
	elif dist==1:
		return 0
	elif dist==l[level]:
		return p[level]
	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: Accepted

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

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

def num_paty(n, f, t):
  global length
  global paty

  if f >= length[n] or t < 0:
    ret = 0
  elif f <= 0 and t >= length[n]-1:
    ret = paty[n]
  else:
    half = length[n] // 2
    ret = 1 if f <= half and t >= half else 0
    ret += num_paty(n-1, f-1, t-1)
    ret += num_paty(n-1, f-half-1, t-half-1)
  return ret

print(num_paty(N, 0, X-1))

Submission status: Accepted

Solution code:
def l(n):
    return 2 ** (n+2) - 3


def p(n):
    return 2 ** (n+1) - 1


def countp(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    if 1 < x <= 1 + l(n-1):
        return countp(n-1, x-1)
    if x == 1 + l(n-1) + 1:
        return p(n-1) + 1
    if 1 + l(n-1) + 1 < x <= 1 + l(n-1) + 1 + l(n-1):
        return p(n-1) + 1 + countp(n-1, x-1-l(n-1)-1)
    return p(n-1) + 1 + p(n-1)


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

Submission status: Accepted

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):
    if level == 0:
        if x==0:
            return(0)
        else:
            return(1)
    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: Accepted

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

def ct(n, x):
    # print(n, x)
    if x == 1:
        if n == 0:
            return 1
        else:
            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: Accepted

Solution code:
def depth(n):
    return 2**(n+2)-3

def totalp(n):
    return 2**(n+1)-1

def eat(n,x):
    if n == 0:
        return x
    elif x <= 1:
        return 0
    elif x >= depth(n)-1:
        return totalp(n)
    elif x == depth(n-1) + 2:
        return totalp(n-1) + 1
    elif x > depth(n-1)+2:
        return totalp(n-1) + 1 + eat(n-1,x-depth(n-1)-2)
    else:
        return eat(n-1,x-1)

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

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
ans = 0
def search(level, i):
	global ans
	#print(level, i, ans)
	if level == 0:
		return ans + 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: Accepted

Solution code:
N,X=map(int,input().split())
PILE=[2**(i+2)-3 for i in range(51)]
def dp(n,x):#レベルnバーガーのx層目まで
    if x==0:
        return 0
    if n==0 and x==1:
        return 1
    if n>=1:
        bp=PILE[n-1]
        if x==1:
            return 0
        elif x<=1+bp:
            return dp(n-1,x-1)
        elif x==2+bp:
            return 1+dp(n-1,bp)
        elif 2+bp<x<=2+2*bp:
            return 1+dp(n-1,bp)+dp(n-1,x-2-bp)
        elif x==3+2*bp:
            return 1+dp(n-1,bp)*2

print(dp(N,X))

Submission status: Accepted

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

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

def B(L, X): #レベルLのバーガーの下からX層にあるパティの数
    if L == 0: return 1
    elif X == 1: return 0
    else:
        if X <= 1 + Num[L-1]:
            return B(L-1, X-1)
        elif X == 2 + Num[L-1]:
            return B(L-1, Num[L-1]) + 1
        elif X <= 2 + 2*Num[L-1]:
            return B(L-1, Num[L-1]) + 1 + B(L-1, X - 2 - Num[L-1])
        elif X == 3 + 2 * Num[L-1]:
            return 2*B(L-1, Num[L-1]) + 1

print(B(N, X))

Submission status: Accepted

Solution code:
def calc(n, k):
	if n == 0:
		return 1
	if k == 1:
		return 0
	len = 2**(n+1)-3 # 1+len+1+len+1
	if k <= len+1:
		return calc(n-1, k-1)
	if k == len+2:
		return calc(n-1, len)+1
	if k <= len+len+2:
		return calc(n-1, len)+1+calc(n-1, k-len-2)
	if k == len+len+3:
		return 2**(n+1)-1

n, k = map(int, input().split())
print(calc(n, k))

Submission status: Accepted

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

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

def burger(l, y):
    if l == 0:
        return y
    if y <= l:
        return 0
    hl = heights[l]
    if y >= hl - l:
        return putties[l]

    if hl // 2 + 1 <= y:
        return putties[l - 1] + 1 + burger(l - 1, y - (hl // 2 + 1))

    return burger(l - 1, y - 1)


print(burger(n, x))

Submission status: Accepted

Solution code:
from functools import lru_cache


N, X = [int(elem) for elem in input().split()]


h_burger = [None] * (N + 1)
h_burger[0] = 1
for i in range(1, N + 1):
    h_burger[i] = 3 + 2 * h_burger[i - 1]

@lru_cache(None)
def num_patti(l, x):
    if x == 0:
        return 0
    elif l == 0:
        return 1
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patti(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return num_patti(l - 1, h_burger[l - 1]) + 1
        else:
            return num_patti(l - 1, h_burger[l - 1]) + 1 \
                 + num_patti(l - 1, x - h_burger[l - 1] - 2)


print(num_patti(N, X))

Submission status: Accepted

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().split())

layers = [1]
patties = [1]

for i in range(1, N+1):
	layer_i = 2 * layers[i-1] + 3
	patty_i = 2 * patties[i-1] + 1
	layers.append(layer_i)
	patties.append(patty_i)
	
def f(n, x):
	if x == 1:
		return 0
		
	elif 1 < x <= 1 + layers[n-1]:
		return f(n-1, x-1)
		
	elif x == 2 + layers[n-1]:
		return patties[n-1] + 1
		
	elif 2 + layers[n-1] < x <= 2 + 2 * layers[n-1]:
		return patties[n-1] + 1 + f(n-1, x-2-layers[n-1])
	elif x == 3 + 2 * layers[n-1]:
		return 2 * patties[n-1] + 1
		
print(f(N, X))N, X = map(int, input().split())

layers = [1]
patties = [1]

for i in range(1, N+1):
	layer_i = 2 * layers[i-1] + 3
	patty_i = 2 * patties[i-1] + 1
	layers.append(layer_i)
	patties.append(patty_i)
	
def f(n, x):
	if x == 1:
		return 0
		
	elif 1 < x <= 1 + layers[n-1]:
		return f(n-1, x-1)
		
	elif x == 2 + layers[n-1]:
		return patties[n-1] + 1
		
	elif 2 + layers[n-1] < x <= 2 + 2 * layers[n-1]:
		return patties[n-1] + 1 + f(n-1, x-2-layers[n-1])
	elif x == 3 + 2 * layers[n-1]:
		return 2 * patties[n-1] + 1
		
print(f(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)

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

Submission status: Runtime Error

Solution code:
# レベルLのN番目
def solve(L,N):
    if L == 0 and N == 1:
        return 1
    if N == 1:
        return 0
    elif N <= 2**(L+1)-2:
        return solve(L-1,N-1)
    elif N == int(2**(L+1)-1):
        return 2**L
    return solve(L-1,N-2**(L+1)+1) + 2**L

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

Submission status: Runtime Error

Solution code:
# レベルLのN番目
def solve(L,N):
    if L == 0 and N == 1:
        return 1
    if N == 1:
        return 0
    elif N <= 2**(L+1)-2:
        return solve(L-1,N-1)
    elif N == int(2**(L+1) - 1):
        return 2**L
    return solve(L-1,N-2**(L+1)+1) + 2**L

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

Submission status: Runtime Error

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

f_dict = {
  0: 1
}
def f(n):
  if f_dict.get(n):
    return f_dict.get(n)
  return (3 + f(n-1) * 2)


patty_dict = {
  0: 1
}
def total_patty(n):
  if patty_dict.get(n):
    return patty_dict.get(n)
  return (1 + 2 * total_patty(n - 1))

def count_patty(n, x):
  if x == 0:
    return 0
  elif 1 <= x and x <= f(n - 1) + 1:
    return count_patty(n - 1, x - 1)
  elif x == f(n - 1) + 2:
    return total_patty(n - 1) + 1
  elif f(n - 1) + 2 <= x and x <= 2 * f(n - 1) + 2:
    return total_patty(n - 1) + 1 + count_patty(n - 1, x - f(n - 1) - 2)
  else:
    return total_patty(n)

print(count_patty(n, x))

Submission status: Runtime Error

Solution code:
memo1 = {}
def f(i):
    if i==0:
        return 1
    if i in memo1:
        return memo1[i]
    memo1[i] = 2*f(i-1)+3
    return memo1[i]
memo2 = {}
def g(i):
    if i==0:
        return 1
    if i in memo2:
        return memo2[i]
    memo2[i]=2*g(i-1)+1
    return memo2[i]
N,X = map(int,input().split())
cnt = 0
while X>0:
    if X>=f(N-1)+2:
        cnt += 1+g(N-1)
        X -= f(N-1)+2
    else:
        X -= 1
    N -= 1
print(cnt)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
    n, x = map(int, input().split())
     
    pate, slice = [1], [1]
    for _ in range(n + 1):
        pate.append(2 * pate[-1] + 1)
        slice.append(2 * slice[-1] + 3)
     
    ans = 0
    while n > 0:
        if x >= slice[n - 1] + 2:
            ans += pate[n - 1] + 1
            x -= slice[n - 1] + 2
        elif x < slice[n - 1] + 2:
            x -= 1
        n -= 1
    print(ans + (x > 0))

Submission status: Runtime Error

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

print(dp[-1][X+1])

Submission status: Runtime Error

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

print(dp[-1][X+1])

Submission status: Runtime Error

Solution code:
N, X = cin()
a = [0 for _ in range(N)] # 全体の枚数
p = [0 for _ in range(N)] # パティの枚数
a[0] = 1
p[0] = 1

for i in range(1, N):
    a[i] = 2 * a[i - 1] + 3
    p[i] = 2 * p[i - 1] + 1
    
def f(N, X):
    if N == 0:  
        if X <= 0: return 0
        else:  return 1
    if X <= 1 + a[N - 1]:  return f(N - 1, X - 1)
    return 1 + p[N - 1] + f(N - 1, X - 2 - a[N - 1])

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

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
N, K = map(int, input().split())
S = [tuple(map(int, input().split())) for _ in range(N)]

S.sort(key=lambda x: -x[1])
st = set()
first_acc, other_acc = [0], [0]
for t, d in S:
  if t in st:
    other_acc.append(other_acc[-1] + d)
  else:
    st.add(t)
    first_acc.append(first_acc[-1] + d)

ans = 0
for i in range(K + 1):
  if len(first_acc) <= i or len(other_acc) <= K - i:
    continue
  ans = max(ans, first_acc[i] + other_acc[K - i] + i * i)

print(ans)

Submission status: Runtime Error

Solution code:
memo1 = {}
def cho(n):
    if n==0:
        return 1
    if n in memo1:
        return memo1[n]
    memo1[n] = 2*cho(n-1)+3
    return memo1[n]
memo2 = {}
def pat(n):
    if n==0:
        return 1
    if n in memo2:
        return memo2[n]
    memo2[n] = 2*pat(n-1)+1
    return memo2[n]
N,X = map(int,input().split())
cnt = 0
k = N
while X>0:
    if X==1:
        break
    elif X==cho(k)//2:
        cnt += pat(k-1)
        break
    elif X<cho(k)//2:
        k -= 1
        X -= 1
    elif X==cho(k)//2+1:
        cnt += 1+pat(k-1)
        break
    else:
        cnt += pat(k-1)+1
        X -= cho(k-1)+2
        k -= 1
print(cnt)

Submission status: Runtime Error

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

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

def mi(x):
    if x == 0:
        return 1
    else:
        return 2*mi(x-1)+3

def bi(x):
    if x == 0:
        return 1
    else:
        return 2*mi(x-1)+1

l = [mi(i) for i in range(N, -1, -1)]
ll = [(val-1)//2 for val in l]
lb = [bi(i) for i in range(N, -1, -1)]

cnt = 0
for i, (li, lli) in enu(zip(l, ll)):
    # print('i', i)
    # print(' li, lli', li, lli)
    if X == li:
        cnt += lb[i]
        break
    if X <= lli:
        X -= 1
    elif X == lli+1:
        cnt += lb[i+1]
        cnt += 1
        break
    else:
        if i == N-1:
            cnt += 1
        else:
            cnt += lb[i+1]
            cnt += 1
            X -= lli
            X -= 1
    # print('  cnt', cnt)
    # print('  X', X)

print(cnt)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, X = mi()
    t = [1<<i for i in range(55)]
    def f(L, x, t):
        if L == 0:
            return 0 if X <= 0 else 1

        if x == 1:
            return 0
        elif 2 <= x <= t[L+1]-2:
            return f(L-1, x-1, t)
        elif x == t[L+1]-1:
            return t[L]
        elif t[L+1] <= x <= t[L+2]-4:
            return t[L]+f(L-1, x-t[L+1]+1, t)
        else:
            t[L+1]-1

    print(f(N, X, t))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(500000)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]


def main():
    N, X = mi()
    t = [1<<i for i in range(55)]
    def f(L, x, t):
        if L == 0:
            return 1

        if x == 1:
            return 0
        elif 2 <= x <= t[L+1]-2:
            return f(L-1, x-1, t)
        elif x == t[L+1]-1:
            return t[L]
        elif t[L+1] <= x <= t[L+2]-4:
            return t[L]+f(L-1, x-t[L+1]+1, t)
        else:
            t[L+1]-1

    print(f(N, X, t))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
# from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

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


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

    print(f(N,X))

    



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

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


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

    print(f(N,X))

    



if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

print(f(n,x))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,  x = map(int, input().split())
b = 'P'
for i in range(n):
    b = 'B' + b + P + b + 'B'
print(b.count('P'))