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

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


def cal_paty(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= b_p[N-1] + 1:
        p_num = cal_paty(N-1, X-1)
        return p_num
    else:
        p_num = p[N-1] + 1
        p_num += cal_paty(N-1, X-(2 + b_p[N-1]))
        return p_num

print(cal_paty(N, X))

Submission status: Accepted

Solution code:
nk_list = list(map(int, input().split()))
n,k = nk_list[0], nk_list[1]

keta_lst = list()
for i in range(50):
    if i == 0:
        keta = 1
        keta_lst.append(keta)
    else:
        keta = 2*keta + 3
        keta_lst.append(keta)

paty_lst = list()
for i in range(50):
    if i == 0:
        paty = 1
        paty_lst.append(paty)
    else:
        paty = 2*paty+1
        paty_lst.append(paty)

def eat_paty(n,k):
    
    if n == 0 and k == 1:
        return 1
    
    keta_before = keta_lst[n-1]
    
    if k == 1:
        return 0
    elif k <= keta_before + 1:
        return eat_paty(n-1, k-1)
    elif k == keta_before + 2:
        return paty_lst[n-1]+1
    elif k <= 2*keta_before + 1:
        return paty_lst[n-1] + 1 + eat_paty(n-1, k-keta_before-2)
    elif k > 2*keta_before + 1:
        return 2 * paty_lst[n-1] + 1

print(eat_paty(n,k))

Submission status: Accepted

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

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

def burger(L, E):
    if L == 0:
        return 1
    if E == 1:
        return 0
    elif E <= t[L-1] + 1:
        return(burger(L-1, E-1))
    elif E == t[L-1] + 2:
        return(p[L-1] + 1)
    elif E <= 2 * t[L-1] + 2:
        return(p[L-1] + 1 + burger(L-1, E-2-t[L-1]))
    else:
        return(2 * p[L-1] + 1)

print(burger(N, X))

Submission status: Accepted

Solution code:
#解答参照した
n,x=map(int,input().split(" "))

P=[1]
M=[1]

for i in range(1,n):
  P.append(2*P[i-1]+1)
  M.append(2*M[i-1]+3)
  
def F(n,x):
  if n==0:
    return 0 if x<=0 else 1
  elif x<=1:
    return 0
  elif 1<x<=M[n-1]+1:
    return F(n-1,x-1)
  elif x==M[n-1]+2:
    return P[n-1]+1
  elif M[n-1]+2<x<2*M[n-1]+3:
    return P[n-1]+1+F(n-1,x-2-M[n-1])
  elif x==2*M[n-1]+3:
    return 2*P[n-1]+1
  else:
    return P[n-1]+1+F(n-1,x-2-M[n-1])
    #print("OH!"+str(n))
    
print (F(n,x))

Submission status: Accepted

Solution code:
N,X = [int(x) for x in input().split()]
# num of Ps
B = [int((2**(n+1))-1) for n in range(N+1)]
# num of layers
C = [int((2**(n+2))-3) for n in range(N+1)]

def count(n,x):
    counter = 0
    center = int((C[n]+1)/2)
    if(n==0):
        return 1
    if(x==1):
        counter = 0
    elif(x==C[n]):
        counter = B[n]
    elif(x==center):
        counter = int((B[n]+1)/2)
    elif(x<center):
        counter = count(n-1,x-1)
    elif(x>center):
        counter = int((B[n]+1)/2) + count(n-1,x-center)
    return counter

print(count(N,X))

Submission status: Accepted

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 f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
	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: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
def burger(x):
    if not x:
        return 1
    return 3 + 2*burger(x-1)
def pate(n,x):
    if not n or not x:
        return [0, 1][x == 1]
    result = 0
    if x == burger(n):
        return 2**(n+1)-1
    if x == 2 + burger(n-1):
        return 2**n-1 + 1
    elif x > (burger(n)+1)//2:
        result += 2**n-1 + 1
        x -= (burger(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())
L = [1]
for i in range(50) :
    L.append(L[-1]*2+3)
def dp(n,x) :
    if x == 0 :
        return 0
    elif n == 0 :
        return 1
    else :
        if x == 1 :
            return 0
        elif x <= L[n-1]+1 :
            return dp(n-1,x-1)
        elif x == L[n-1]+2 :
            return dp(n-1,x-1)+1
        elif x <= L[n]-1 :
            return dp(n-1,x-1)+1+dp(n-1,x-L[n-1]-2)
        else :
            return dp(n-1,x-1)*2+1
ans = dp(N,X)
print(ans)

Submission status: Accepted

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

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

def dp(n,x) :
    if x == 0 :
        return 0
    elif n == 0 :
        return 1
    elif n >= 1 :
        if x == 1 :
            return 0
        elif x <= L[n-1]+1 :
            return dp(n-1,x-1)
        elif x == L[n-1]+2 :
            return dp(n-1,x-1)+1
        elif x <= L[n]-1 :
            return dp(n-1,x-1)+1+dp(n-1,x-L[n-1]-2)
        else :
            return dp(n-1,x-1)*2+1
ans = dp(N,X)
print(ans)

Submission status: Accepted

Solution code:
n, x = (int(i) for i in input().split())

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

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

print(f(n,x))

Submission status: Accepted

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

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

Solution code:
n, x = map(int, input().split())
def get_len(lv):
  m = 1
  for i in range(lv):
    m = m * 2 + 3
  return m  
def count_p(lv, p):
  if p <= lv:return 0
  elif lv == 0:return 1
  m = get_len(lv)
  if p > (m-1)/2:
    return (m-1)/2 + 1 - count_p(lv, m-p)
  else:
    return count_p(lv-1,p-1)
print(int(count_p(n, x)))

Submission status: Accepted

Solution code:
n, x = [int(i) for i in input().split()]

num_p = [0 for i in range(n+1)]

for i in range(1, n+1):
  num_p[i] = num_p[i-1] * 2 + 1

total = 1
for i in range(1, n + 1):
  total = total * 2 + 3

cnt = 0
left = 1
right = total

for i in range(n,-1, -1):
  center = (left + right) // 2
  if x == center:
    cnt += num_p[i] + 1
    break
  if x > center:
    cnt += num_p[i] + 1
    left = center + 1
    right = right - 1
  else:
    left = left + 1
    right = center -1

print(cnt)

Submission status: Accepted

Solution code:
a = list(map(int, input().split()))
c = a[1]
res = 0

b = [[5,3,1]]
for i in range(1,a[0]):
    tmp = [b[i-1][0]*2+3,b[i-1][1]*2+1,i+1]
    b.append(tmp)

for i in range(a[0]-1,-1,-1):
    if b[i][0] * 2 + 1 <= c:
        c = c - b[i][0]*2 - 1
        res = res + b[i][1] * 2 + 1
    elif b[i][0] <= c: 
        c = c - b[i][0]
        res = res + b[i][1]
        if c > 0:
            c = c - 1
            res = res + 1
    c = c - 1

if c > 0:
    res = res + c

print(res)

Submission status: Accepted

Solution code:
N,X =map(int,input().split())
pa =[1]
bu =[1]
for i in range(N-1):
    pa.append(pa[i]*2+1)
    bu.append(bu[i]*2+3)
ans = 0
for i in range(N):
    if X >= bu[N-1-i]*2+2:
        ans += 2*pa[N-1-i]+1
        break
    elif X >= bu[N-1-i]+2:
        ans += pa[N-1-i]+1
        X -= bu[N-1-i]+2
    elif X == bu[N-1-i]+1:
        ans += pa[N-1-i]
        break
    else:
        X -= 1
print(ans)

Submission status: Accepted

Solution code:
N,X = list(map(int,input().split()))
a = [1]
p = [1]
def f(n,x):
    if x == 1:
        if n == 0:return 1
        else:return 0
    elif 1 < x and x < 2+a[n-1]:
        return f(n-1,x-1)
    elif 2+a[n-1] == x:
        return 1 + p[n-1]
    elif 2+a[n-1] < x and x < 3+2*a[n-1]:
        return p[n-1]+1+f(n-1,x-2-a[n-1])
    else:
        return 2*p[n-1]+1


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

print(f(N,X))

Submission status: Accepted

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

a, p = [1], [1]

def main():
    N, X = [int(x) for x in stdin.readline().rstrip().split()]
    for i in range(N):
        a.append(a[i] * 2 + 3)
        p.append(p[i] * 2 + 1)

    print(f(N, X))

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X = map(int, input(). split())
a, p = [1], [1]

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

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

print(xmas(N, X))

Submission status: Accepted

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

a=[0]*n
p=[0]*n

a[0]=1
p[0]=1

for i in range(1,n):
  a[i]=3+2*a[i-1]
  p[i]=1+2*p[i-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-a[n-1]-2)

print(f(n,x))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
a = [1]
p = [1]
for i in range(N):
    a.append(2*a[-1] + 3)
    p.append(2*p[-1] + 1)
def f(N, X):
    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: Accepted

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

# AtCoder Beginner Contest 115：D - Christmas


# 各レベルの長さ
L = [1]+[0]*50
for i in range(50):
    L[i+1] = 3+L[i]*2
# print L

# 各レベルに含まれるパティの数
P = [1]+[0]*50
for i in range(50):
    P[i+1] = 1+P[i]*2
# print P


# 'B' + L[l-1] + 'P' + L[l-1] + 'B'
def lp(l, n):
    if l == 0:
        return 1
    elif n == 1:
        # 'B'
        return 0
    elif 1 < n <= 1+L[l-1]-1:
        # 'B' + L[l-1]の一つ手前まで
        return lp(l-1, n-1)
    elif n == 1+L[l-1]:
        # 'B' + L[l-1]
        return P[l-1]
    elif n == 1+L[l-1]+1:
        # 'B' + L[l-1] + 'P'
        return P[l-1]+1
    elif 1+L[l-1]+1 < n <= 1+L[l-1]+1+L[l-1]-1:
        # 'B' + L[l-1] + 'P' + L[l-1]の一つ手前まで
        return P[l-1] + 1 + lp(l-1, n-(1+L[l-1]+1))
    elif n == 1+L[l-1]+1+L[l-1]:
        # 'B' + L[l-1] + 'P' + L[l-1]
        return P[l-1] + 1 + P[l-1]
    elif n == 1+L[l-1]+1+L[l-1]+1:
        # 'B' + L[l-1] + 'P' + L[l-1] + 'B'
        return P[l-1] + 1 + P[l-1]
    else:
        print 'NG!'
        exit()


def main():
    N, X = [int(i) for i in raw_input().strip().split(' ')]

    print lp(N, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X = list(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 check(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1

    if x <= 1 + a[n - 1]:
        return check(n - 1, x - 1)

    return p[n - 1] + 1 + check(n - 1, x - 2 - a[n - 1])


def main():
    print(check(N, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Christmas Eve

q = [1]
for i in range(50):
    q.append(q[i] * 2 + 1)

def n_down(n, x, s):
    global q

    if n == 1:
        s.append('bpppb'[:x].count('p'))
        return(0, 0, s)

    if x < q[n]:
        return(n - 1, x - 1, s)
    elif x == q[n]:
        s.append(q[n - 1] + 1)
        return(0, 0, s)
    else:
        s.append(q[n - 1] + 1)
        return(n - 1, x - q[n], s)

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

while n:
    n, x, s = n_down(n, x, s)

print(sum(s))

Submission status: Accepted

Solution code:
#coding:utf-8
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 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: Accepted

Solution code:
#!/usr/bin/env python3

from functools import lru_cache

NMAX = 50

@lru_cache(maxsize=1)
def get_sizes():
    res = [1]
    for i in range(1, NMAX + 1):
        res.append(res[-1] * 2 + 3)
    return tuple(res)

@lru_cache(maxsize=1000)
def eat_m_layers_of_level_k(k, m, si):
    assert 0 < m <= si[k]
    if k == 0:
        pats = 1
        buns = 0
    else:
        sublev = si[k - 1]
        pp, bb = eat_m_layers_of_level_k(k - 1, si[k - 1], si)
        if m == 1:
            pats = 0
            buns = 1
        elif 1 < m <= 1 + sublev:
            p, b = eat_m_layers_of_level_k(k - 1, m - 1, si)
            pats = p
            buns = b + 1
        elif m == 2 + sublev:
            pats = pp + 1
            buns = bb + 1
        elif 2 + sublev < m <= 2 + 2 * sublev:
            p, b = eat_m_layers_of_level_k(k - 1, m - si[k - 1] - 2, si)
            pats = pp + p + 1
            buns = bb + b + 1
        elif m == si[k]:
            pats = 2 * pp + 1
            buns = 2 * bb + 2
        else:
            raise ValueError
    return pats, buns

def main():
    n, x = map(int, input().split())
    si = get_sizes()
    p, b = eat_m_layers_of_level_k(n, x, si)
    print(p)

main()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(50000)


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

sum_berger = {0: 1}


# 考え方 xがレベルいくつのバーガーのどの位置かを考える
# レベルnのバーガー = "B" + レベルn-1のバーガー + "P" + レベルn-1のバーガー + "B"
# という式から再帰的にどのバーガーにいるかを考える。
def recursive(n):
    if n in sum_berger.keys():
        return sum_berger[n]
    else:
        sum_berger[n] = 1 + recursive(n - 1) + 1 + recursive(n - 1) + 1
        return sum_berger[n]


patties = {0: 1}


def patti(n):
    if n in patties.keys():
        return patties[n]
    else:
        patties[n] = patti(n - 1) * 2 + 1
        return patties[n]


def answer(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x == sum_berger[n]:
        return patties[n]
    elif x < sum_berger[n] // 2+1:
        return answer(n-1, x-1)
    elif x == sum_berger[n] // 2 + 1:
        return patties[n] // 2 + 1
    elif x > sum_berger[n] // 2 + 1:
        return answer(n-1, x-(sum_berger[n] // 2 + 1)) + patties[n] // 2 + 1


patti(50)
recursive(50)

print(answer(n, x))
# BBBBPPPBPBPPPBBPBBPPPBPBPPPBBBPBBBPPPBPBPPPBBPBBPPPBPBPPPBBBB
# BBBPPPBPBPPPBBPBBPPPBPBPPPBBB
# BBPPPBPBPPPBB
# BPPPB
# P

Submission status: Accepted

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

number = 0

while not X == 0:
    for x in range(N,-1,-1):
        if 2**(x+2)-3 <= X-N+x:
            number = number + 2**(x+1) -1 
            X = X-N+x-2**(x+2)+3
            N = x
            if X >= 1:
                X = X-1 
                number = number + 1
                break
            else:
                break
        if x == 0:
            X = 0 
            break
else:
    print(number)

Submission status: Accepted

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

a,p = [1],[1]

#バーガーの厚みとパティの総数を求める

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

def f(N,X):
    if N == 0:
        if X <= 0:
            return 0

        else:
            return 1

    elif X <= 1 + a[N-1]:
        return f(N -1,X-1)

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

print(f(n,x))

Submission status: Accepted

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

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

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


print(f(N, X))

Submission status: Accepted

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

Submission status: Accepted

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

L = [1]
P = [1]

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

def Heap(now_L, Goal):
    if now_L == 0:
        if Goal <= 0:
            return 0
        else:
            return 1
    elif Goal < L[now_L-1] + 2:
        return Heap(now_L-1, Goal-1)
    else:
        return P[now_L-1] + 1 + Heap(now_L-1, Goal-L[now_L-1]-2)
    
print(Heap(N, X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#D
N, X = [int(x) for x in input().split()]

def make(lv):
    if lv==0: return 'P'
    else: return 'B' + make(lv-1) + 'P' + make(lv-1) + 'B'

def countBurg(lv):
    if lv==0: return 1, 1
    else: #return 'B' + make(lv-1) + 'P' + make(lv-1) + 'B'
        c1 = countBurg(lv-1)
        return 1+c1[0]+1+c1[0]+1, c1[1]+1+c1[1]

def countBurg2(lv):
    count = [(1,1) for i in range(lv+1)]
    for i in range(1,lv+1):
        count[i] = count[i-1][0]*2+3, count[i-1][1]*2+1
    return count

BurgCount = countBurg2(50) #[(bc, pc),...]

def countPate(lv, x):
    #print(lv, x) #
    if lv<=0: return 1

    ec = 1 # Eat Count   B
    epc = 0 # Eat Pate Count
    #print(ec, epc) #
    if ec>=x: return epc
    
    if ec+BurgCount[lv-1][0]>x:
        epc += countPate(lv-1, x-ec)
        ec = x #lv-1
    else:
        ec += BurgCount[lv-1][0]#lv-1
        epc += BurgCount[lv-1][1]
    #print(ec, epc) #
    if ec>=x: return epc
    
    ec += 1 #P
    epc += 1 
    #print(ec, epc) #
    if ec>=x: return epc
    
    if ec+BurgCount[lv-1][0]>x:
        epc += countPate(lv-1, x-ec)
        ec = x #lv-1
    else:
        ec += BurgCount[lv-1][0]#lv-1
        epc += BurgCount[lv-1][1]
    #print(ec, epc) #
    if ec>=x: return epc
    
    ec += 1 #B
    #print(ec, epc) #
    return epc
            
#burg = make(N)
#print(burg)#
#for i in range(X):
#    if burg[i]=='P': count += 1

#print(BCount)#

print(countPate(N,X))

Submission status: Accepted

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

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

def solve(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 1
    b = count_b(n-1)
    if x < (b + 1):
        return solve(n-1, x-1)
    return count_p(n-1) + (1 if x >= (b + 2) else 0) + solve(n-1, x-b-2)

def main():
    n, x = list(map(int, input().split()))
    print(solve(n, x))

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math

def sizeN(n):
    count = 1
    for i in range(n):
        count = count*2 + 3
    return count


def countP(n):
    if n < 0:
        return 0
    count = 1
    for i in range(n):
        count = count*2 + 1
    return count


def sharpen(x):
    return x - 1


def answer(N, X):
    count_p = 0
    x = X
    for n in range(N,-1,-1):
        if x < math.ceil(sizeN(n)/2):
            x = sharpen(x)
        else:
            x = sharpen(x - math.floor(sizeN(n)/2))
            count_p += countP(n-1)+1
    return count_p


if __name__ == '__main__':

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

Submission status: Accepted

Solution code:
def m(n): # n次元バーガーの層数
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a = a * 2 + 3
        return a

def paty(n): # n次元バーガーのパティの数
    a = 1
    if n >= 1:
        for i in range(n):
            a = a * 2 + 1
    return a

def a(n, x): #これが答えを返す
    x = x - 1
    if x == 0 and n == 0:
        return 1
    elif x == 0:
        return 0
    elif x == m(n-1) + 1:
        return paty(n-1) + 1
    elif x == m(n):
        return paty(n)
    elif x > m(n-1):
        return paty(n-1) + 1 + a(n - 1, x - m(n-1) - 1)
    else:
        n = n - 1
        return a(n, x)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
a = [1]
b = [1]
for i in range(50):
  a += [2*a[-1]+3]
  b += [2*b[-1]+1]
  
def ans(N, X):
  if N == 0 : return X
  if X == 1 : return 0
  if X == a[N]: return b[N]
  if X == (a[N]+1)//2 : return 1 + b[N-1]
  if X < (a[N]+1)//2:
    return ans(N-1, X-1)
  else:
    return 1+b[N-1] + ans(N-1, X-(a[N]+1)//2)

print(ans(N,X))

Submission status: Accepted

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 f(n, x):
    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: Accepted

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if n == 0:
        return 0 + (x >= 1)

    # レベルL-1バーガー
    elif x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 2つ目のレベルL-1バーガーにかかる
    else:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)


print(solve(N, X))

Submission status: Accepted

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン(ただしレベル0バーガー参照時には+1)
        return 0 + (n == 0)

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        return patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x <= 2 * thick[n - 1] + 2:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    elif x == 2 * thick[n - 1] + 3:
        return 2 * patti[n - 1] + 1


print(solve(N, X))

Submission status: Accepted

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 f(N, X): # X <= 0 や X > a_N を許容し解説本文から簡略化
    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: Accepted

Solution code:
def ans(n, x):
	if n < 0:
		return 0
	if x < 1:
		return 0
	if x < 2 ** (n + 1) - 1:
		return ans(n - 1, x - 1)
	if x == 2 ** (n + 1) - 1:
		return 2 ** n
	return 2 ** n + ans(n - 1, x - 2 ** (n + 1) + 1)
N, X = map(int, input().split())
print(ans(N, X))

Submission status: Accepted

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

Solution code:
n, x = map(int, input().split())
layer = [1]
patty = [1]
for _ in range(n):
    layer.append(1 + layer[-1] + 1 + layer[-1] + 1)
    patty.append(patty[-1] + 1 + patty[-1])
res = 0
while x > 0:
    x -= 1
    if x >= layer[n-1] + 1:
        res += 1
    while x >= layer[n-1]:
        res += patty[n-1]
        x -= layer[n-1] + 1
    n -= 1
print(res)

Submission status: Accepted

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

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


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

    if x == 1:
        return 0
    elif x > 1 and x <= counts[n-1] + 1:
        return req(n - 1, x - 1)
    elif x == counts[n-1] + 2:
        return req(n - 1, counts[n-1]) + 1
    else:
        if x == 2*counts[n-1] + 3:
            return req(n-1, counts[n-1]) * 2 + 1
        else:
            return req(n-1, x - (counts[n-1] + 2)) + req(n - 1, counts[n-1]) + 1


print(req(N, X))

Submission status: Accepted

Solution code:
def solve(N, X):
    thickness = [1]
    pate = [1]
    for L in range(1, N + 1):
        thickness.append(thickness[-1] * 2 + 3)
        pate.append(pate[-1] * 2 + 1)

    def sub(t, X):
        middle = (thickness[t] - 1) // 2
        if t == 0:
            return 1
        if X <= 0:
            return 0
        if X < middle:
            return sub(t - 1, X - 1)
        if X == middle:
            return pate[t - 1] + 1
        return pate[t - 1] + 1 + sub(t - 1, X - middle - 1)

    return sub(N, X - 1)

def test():
    def f(N, X, expect):
        print('N={}, X={}'.format(N, X))
        print(solve(N, X), 'expect={}'.format(expect))
    f(2, 7, 4)
    f(2, 8, 4)
    f(2, 9, 5)
    f(50, 4321098765432109, 2160549382716056)

    print('-'*5)
    for i in range(1, 14): f(2, i, '')

    print('-'*5)
    for i in range(1, 6): f(1, i, '')


if __name__ == '__main__':
    N, X = map(int, input().split())
    print(solve(N, X))

Submission status: Accepted

Solution code:
g_memo = {0: 1}
h_memo = {0: 1}

def g(l):
    if not l in g_memo:
        g_memo[l] = 3 + 2*g(l-1)
    return g_memo[l]

def h(l):
    if not l in h_memo:
        h_memo[l] = 1 + 2*h(l-1)
    return h_memo[l]

def solve(l, x):
    if x <= 0:
        return 0
    if l == 0: # x > 0
        return 1
    if x >= g(l):
        return h(l)
    res = 0
    y = 1
    # f(l-1)
    res += solve(l-1, x-y)
    y += g(l-1)
    # P
    res += int(y < x)
    y += 1
    # f(l-1)
    res += solve(l-1, x-y)
    return res

n, x = map(int, raw_input().split())
print(solve(n, x))

Submission status: Accepted

Solution code:
g_memo = {0: 1}
h_memo = {0: 1}
dp = {}

def g(l):
    if not l in g_memo:
        g_memo[l] = 3 + 2*g(l-1)
    return g_memo[l]

def h(l):
    if not l in h_memo:
        h_memo[l] = 1 + 2*h(l-1)
    return h_memo[l]

def solve(l, x):
    if x <= 0:
        return 0
    if l == 0: # x > 0
        return 1
    if x >= g(l):
        return h(l)
    if (l, x) in dp:
        return dp[l,x]
    y = 0
    res = 0
    # B
    y += 1
    # f(l-1)
    res += solve(l-1, x-y)
    y += g(l-1)
    # P
    if y < x: # P
        res += 1
    y += 1
    # f(l-1)
    res += solve(l-1, x-y)
    y += g(l-1)
    # B 
    y += 1

    dp[l,x] = res
    return res

n, x = map(int, raw_input().split())
print(solve(n, x))

Submission status: Accepted

Solution code:
n, x = [int(i) for i in input().split()]

def tlen(L):
    l = 1
    for i in range(1, L):
        l = l*2 + 3
    return l

def tpat(L):
    p = 1
    for i in range(1, L):
        p = p*2 + 1
    return p

def maisu(n, x):
    tl = tlen(n)
    if x == 1:
        return(0)
    elif n == 1:
        b = "bpppb"
        b = b[:x]
        return(b.count("p"))
    elif 2 <= x <= 1+tl-1:
        return(maisu(n-1, x-1))
    elif x == 1+tl:
        return(tpat(n))
    elif x == 2+tl:
        return(tpat(n)+1)
    elif tl+3 <= x <= 1+tl*2:
        return(tpat(n)+1+maisu(n-1,x-2-tl))
    else:
        return(tpat(n)*2+1)  

print(maisu(n,x))

Submission status: Accepted

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

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

print(task(n,x))

Submission status: Accepted

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

a = [2**(n+2)-3 for n in range(51)]
b = [2**(n+1)-1 for n in range(51)]

def func(n, x):
    if n == 0:
        return 1
    if x == 1:
        return 0
    if 2 <= x < 2+a[n-1]:
        return func(n-1, x-1)
    if x == 2+a[n-1]:
        return 1+b[n-1]
    if 3+a[n-1] <= x < 3+2*a[n-1]:
        return 1+b[n-1]+func(n-1, x-(2+a[n-1]))
    else:
        return 1+2*b[n-1]

print(func(N, X))

Submission status: Accepted

Solution code:
Pat=[1]
All=[1]
for i in range(51):
    Pat.append(Pat[i]*2+1)
    All.append(All[i]*2+3)

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

def saiki(N,X):
    if N==0:
        if X<=0:
            return 0
        else:
            return 1
    elif X<=All[N-1]+1:
        return saiki(N-1,X-1)
    elif X<=All[N]-1:
        return Pat[N-1]+1+saiki(N-1,X-2-All[N-1])
    else:
        return Pat[N]
        
print(saiki(N,X))