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:
def do(level,x):
    if x<=0: #1層も手を付けないとき
        return 0
    elif x>=whole[level]: #完食できるとき
        return patty[level]
    #それ以外、途中まで食べるときはlevel>=1の場合のみあり得る
    x-=1 #このとき1層目は必ずバンズ
    res=0 #食べたパティの総数を記録する
    if x>=whole[level-1]+1: #真ん中のパティまで到達できるとき
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1, 5, 13, 29, 61, 125, 253, 509, 1021, 2045, 4093, 8189, 16381, 32765, 65533, 131069, 262141, 524285, 1048573, 2097149, 4194301, 8388605, 16777213, 33554429, 67108861, 134217725, 268435453, 536870909, 1073741821, 2147483645, 4294967293, 8589934589, 17179869181, 34359738365, 68719476733, 137438953469, 274877906941, 549755813885, 1099511627773, 2199023255549, 4398046511101, 8796093022205, 17592186044413, 35184372088829, 70368744177661, 140737488355325, 281474976710653, 562949953421309, 1125899906842621, 2251799813685245, 4503599627370493]
patty=[1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767, 65535, 131071, 262143, 524287, 1048575, 2097151, 4194303, 8388607, 16777215, 33554431, 67108863, 134217727, 268435455, 536870911, 1073741823, 2147483647, 4294967295, 8589934591, 17179869183, 34359738367, 68719476735, 137438953471, 274877906943, 549755813887, 1099511627775, 2199023255551, 4398046511103, 8796093022207, 17592186044415, 35184372088831, 70368744177663, 140737488355327, 281474976710655, 562949953421311, 1125899906842623, 2251799813685247]
print(do(n,x))

Submission status: Accepted

Solution code:
def do(level,x):
    if x<=0: #1層も手を付けないとき
        return 0
    elif x>=whole[level]: #完食できるとき
        return patty[level]
    #それ以外、途中まで食べるときはlevel>=1の場合のみあり得る
    x-=1 #このとき1層目は必ずバンズ
    res=0 #食べたパティの総数を記録する
    if x>=whole[level-1]+1: #真ん中のパティまで到達できるとき
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1]+[0]*50
patty=[1]+[0]*50
for i in range(1,n+1):
    whole[i]=whole[i-1]*2+3
    patty[i]=patty[i-1]*2+1
res=0
print(do(n,x))

Submission status: Accepted

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

def buns(L):
    if L == 0:#再帰終了条件
        B[L] = 0
        return B[L]
    else:
        if B[L] == -1:
            B[L] = buns(L-1)*2 + 2
            return B[L]
        else:
            return B[L]

def patty(L):
    if L == 0:#再帰終了条件
        P[L] = 1        
        return P[L]
    else:
        if P[L] == -1:
            P[L] = patty(L-1)*2 + 1
            return P[L]
        else:
            return P[L]


buns(N)
patty(N)
memo = [B[i] + P[i] for i in range(51)]

def func(L,X):

    if L == 0:
        if X <= 0:
            return 0
        else:
            return 1
    elif X <= memo[L-1]+1:
        return func(L-1,X-1)
    else :
        return P[L-1] + 1 + func(L-1,X-2-memo[L-1])


print(func(N,X))

Submission status: Accepted

Solution code:
def do(level,x):
    if x<=0:
        return 0
    elif x>=j[level]:
        return k[level]
    res=0
    x-=1
    if x>=j[level-1]+1:
        x-=j[level-1]+1
        res+=k[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
j=[1]+[0]*50
k=[1]+[0]*50
for i in range(1,n+1):
    j[i]=j[i-1]*2+3
    k[i]=k[i-1]*2+1
res=0
print(do(n,x))

Submission status: Accepted

Solution code:
def do(level,x):
    if x<=0:
        return 0
    if level==0:
        return 1
    res=0
    x-=1
    if x>j[level-1]:
        x-=j[level-1]+1
        res+=k[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
j=[1]+[0]*50
k=[1]+[0]*50
for i in range(1,n+1):
    j[i]=j[i-1]*2+3
    k[i]=k[i-1]*2+1
res=0
print(do(n,x))

Submission status: Accepted

Solution code:
import math
N,X = list(map(int, input().split()))
cnt = 0
for i in range(N, 0, -1):
  t = math.pow(2, i + 1) - 2
  if X >= t * 2:
    cnt += t + 1
    break
  elif X >= t:
    cnt += t / 2
    X -= t
    if X > 1:
      cnt += 1
      X -= 1
    elif X == 1:
      cnt += 1
      break
    else:
      break
  else:
    if X > 1:
      X -= 1
    else:
      break
print(int(cnt))

Submission status: Accepted

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

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


def f(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + size[n - 1]:
        return f(n - 1, x - 1)
    else:
        return p_num[n - 1] + 1 + f(n - 1, x - 2 - size[n - 1])  # x - 1 - size[n - 1] - 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): # 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:
n,x = map(int, input().split())

p, a = [1], [1]

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

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

print(f(n,x))

Submission status: Accepted

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


def simple(l):
    if not l:
        return "P"
    mid = simple(l - 1)
    return "B{}P{}B".format(mid, mid)


def length(l):
    return -2 + (1 - 2**(l + 2)) // (1 - 2)


def plen(l):
    return (1 - 2**(l + 1)) // (1 - 2)


def check(x, left, center, right, result):
    if x < center:
        if x == left:
            pos = -2
        else:
            return -1
    elif x > center:
        if x == right:
            pos = 2
        else:
            return 1
    else:
        pos = 0
    if pos in [-2, 0, 2]:
        if pos == -2:
            # print("end left")
            pass
        elif pos == 2:
            # print("end right")
            result += plen(depth + 1)
        else:
            # print("end center", plen(depth), depth)
            result += plen(depth) + 1
        print(result)
        # print(s[:k + 1].count("P"))
        exit()
k -= 1
# s = simple(n)
# print(s[:k], s[k], s[k + 1:])
# print(" - - - - - ", length(1))

left = 0
right = length(n)
center = (left + right) // 2
result = 0
depth = n - 1
# tmp = s
for i in range(50):
    # print(left, center, right, "depth", depth)
    # print(s[:center], s[center], s[center + 1:])
    # tmp = s[left : right + 1]
    # if len(tmp) != 3:
    #     print(tmp[0], tmp[1:len(tmp) // 2], tmp[len(tmp) // 2], tmp[len(tmp) // 2 + 1:-1], tmp[-1])
    # else:
    #     print("P P P")

    pos = check(k, left, center, right, result)
    if pos == -1:
        if depth == 0:
            print(result + 1)
            exit()
        left += 1
        right = center - 1
        center = (left + right) // 2
        # print("left")
    else:
        if depth == 0:
            print(result + 3)
            exit()
        right -= 1
        left = center + 1
        center = (left + right) // 2
        result += plen(depth) + 1
    #     print("right", result, plen(depth) + 1)
    # print()
    depth -= 1

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
# a:バンの数  b:パティの数
a,b = [1],[1]
for i in range(N):
    a.append(2*a[i] + 3)
    b.append(2*b[i] + 1)
def f(N,X):
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif 1 < X <= a[N-1] + 1:
        return f(N-1,X-1)
    elif X == a[N-1] + 2:
        return b[N-1] + 1
    elif a[N-1] + 2 < X <= 2*a[N-1] + 2:
        return b[N-1] + 1 + f(N-1,X-(a[N-1]+2))
    elif X == 2*a[N-1] + 3:
        return 2*b[N-1] + 1
ans = f(N,X)
print(ans)

Submission status: Accepted

Solution code:
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])


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(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:
def d_christmas(N, X):
    # レベルnのときのパティの総数をp_nと書くと、 p_{n+1} = p_n + 1 + p_n, p_0 = 1
    # レベルnのときのバーガーの層数をa_nと書くと、 a_{n+1} = 1 + a_n + 1 + a_n + 1, a_0 = 1
    a, p = [1], [1]
    for _ in range(N):
        a.append(a[-1] * 2 + 3)
        p.append(p[-1] * 2 + 1)

    def f(n, x):
        # レベルnバーガーの下からn層食べたとき、食べたパティの数
        if n == 0:
            return 0 if x <= 0 else 1  # パティが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])

    return f(N, X)

N, X = [int(i) for i in input().split()]
print(d_christmas(N, X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[0]
for i in range(n):
  l.append(2**(i+1)-1)
m=[0]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  t=2**(i+1)-1
  if x<t:
    x-=1
  elif x==t:
    c+=l[i]+1
    x=0
  else:
    c+=l[i]+1
    if x==m[i+1]:
      x-=1
    x=x-t
print(c)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[0]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[0]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    c+=l[i]+1
    x=0
  elif x>2**(i+1)-1:
    c+=l[i]+1
    if x==m[i+1]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)

Submission status: Accepted

Solution code:
def feed_runrun(answer, burger_dimension, appetite):
    if appetite == 0:
        return answer

    burger_size = 2 ** (burger_dimension + 2) - 3
    # 食べきれない
    if appetite < burger_size:
        return feed_runrun(answer, burger_dimension - 1, appetite - 1)
    # 食べきれる
    amount_of_p = 2 ** (burger_dimension + 1) - 1
    if appetite >= burger_size + 1:
        return feed_runrun(answer + amount_of_p + 1, burger_dimension, appetite - burger_size - 1)
    return feed_runrun(answer + amount_of_p, burger_dimension, appetite - burger_size)


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

Submission status: Accepted

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

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

def a(n):
    return 2**(n+2)-3

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:
#!/mnt/c/Users/moiki/bash/env/bin/python
N, X = map(int, input().split())

    
L = [1]
P = [1]

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

        
    
def calc_pan(n,x):
    # c = judge(n,x)
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + L[n-1]:
        return calc_pan(n-1, x-1)
    else:
        return P[n-1] + 1  + calc_pan(n-1, x - 2 - L[n-1])

sum = calc_pan(N, X)
print(sum)

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_patties(l, x):
    if x == 0:
        return 0
    elif l == 0:
        return 1
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patties(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return num_patties(l - 1, h_burger[l - 1]) + 1
        else:
            return num_patties(l - 1, h_burger[l - 1]) + 1 \
                 + num_patties(l - 1, x - h_burger[l - 1] - 2)


print(num_patties(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
    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(2*a[i]+3)
    p.append(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-2-a[n-1])
print(f(n, x))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
L=[0]*(N+1)
t=1
L[0]=t
for i in range(1,N+1):
    t=2*t+3
    L[i]=t
M=[0]*(N+1)
s=1
for i in range(1,N+1):
    s=2*s+1
    M[i]=s
a=X
ans=0
for i in range(N-1,0,-1):
    t=L[i]
    s=M[i]
    if a==1:
        a-=1
        break
    elif 2<=a<=t+1:
        a-=1
    elif a==t+2:
        a-=t+2
        ans+=s+1
        break
    elif t+3<=a<=2*t+2:
        ans+=s+1
        a=a-(t+2)
    elif a==2*t+3:
        a-=2*t+3
        ans+=2*s+1
        break
#print('g',i,ans,a,X)
if 0<=a<=4:
    ans+=max(a-1,0)
else:
    ans+=3
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

def main():
	n,x=map(int,input().split())
	ans = 0
	for i in range(n, -1, -1):
		if x == 0:
			break
		m = 4*(2**i)-3
		if x == m:
			ans += 2**(i+1) - 1
			break
		if x >= (m+1)/2:
			ans += 2**(i)
			x -= int((m+1)/2)
		else:
			x -= 1
	print(ans)
	return
main()

Submission status: Accepted

Solution code:
p = [1]*51
t = [1]*51
def f(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    if x==t[n]:
        return p[n]
    if x==p[n]:
        return p[n-1]+1
    if x<p[n]:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-p[n])+1

for i in range(1,51):
    p[i] = p[i-1]*2+1
    t[i] = t[i-1]*2+3
n,x = map(int,input().split())    
print(f(n,x))

Submission status: Accepted

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

sum_p = [1]
sum_dim = [1]

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


def cal(n, rem):
    if n == 0:
        return 0 if rem<= 0 else 1
    elif rem <= 1 + sum_dim[n-1]:
        return cal(n - 1, rem - 1)
    else:
        return sum_p[n-1] + 1 + cal(n - 1, rem - 2 - sum_dim[n-1])


print(cal(n, x))

Submission status: Accepted

Solution code:
a = [1 for i in range(51)]
p = [1 for i in range(51)]


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


def main():
    N, X = map(int, input().split())
    for i in range(N):
        a[i+1] = 2 * a[i] + 3
        p[i+1] = 2 * p[i] + 1
    ans = get(N, X)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

P = [1]
H = [1]
for i in range(1,51):
    P.append(P[i-1]*2+1)
    H.append(H[i-1]*2+3)

def r(n,x):
    if x<=n:
        return 0
    if x==H[n]:
        return P[n]
    if x>=H[n-1]+2:
        return P[n-1]+1+r(n-1,x-H[n-1]-2)
    else:
        return r(n-1,x-1)

print(r(N,X))

Submission status: Accepted

Solution code:
p = [1]*51
t = [1]*51
def f(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    if x==t[n]:
        return p[n]
    if x==p[n]:
        return p[n-1]+1
    if x<p[n]:
        return f(n-1,x-1)
    return p[n-1]+f(n-1,x-p[n])+1

for i in range(1,51):
    p[i] = p[i-1]*2+1
    t[i] = t[i-1]*2+3
n,x = map(int,input().split())    
print(f(n,x))

Submission status: Accepted

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

def a(L):
    if L == 0:
        return 1
    return 2 * a(L-1) + 3

def p(L):
    if L == 0:
        return 1
    return 2 * p(L-1) + 1

def solve(L, X):
    if L == 0:
        return 0 if X == 0 else 1
    if X == 1:
        return 0
    if 1 < X <= 1 + a(L-1):
        return solve(L-1, X-1)
    if X == 2 + a(L-1):
        return p(L-1) + 1
    if 2 + a(L-1) < X <= 2 + 2 * a(L-1):
        return p(L-1) + 1 + solve(L-1, X-a(L-1)-2)
    if X == 3 + 2 * a(L-1):
        return 2 * p(L-1) + 1

print(solve(N, X))

Submission status: Accepted

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

from sys import stdin, stderr

DPL = [0] * 56
DPP = [0] * 56

def F(n, x):
   if x == 0:
      return 0

   if x == 1:
      return 1 if n == 0 else 0

   if x == DPL[n]:
      return DPP[n]

   if x == 1 + DPL[n-1] + 1:
      return DPP[n-1] + 1
   elif x > 1 + DPL[n-1] + 1:
      return DPP[n-1] + 1 + F(n-1, x - (1 + DPL[n-1] + 1))
   else:
      return F(n-1, x-1)

def main():
   N, X = map(int, stdin.readline().split())

   DPL[0] = 1
   DPP[0] = 1
   for n in xrange(1, N+1):
      DPL[n] = 2*DPL[n-1] + 3
      DPP[n] = 2*DPP[n-1] + 1

   res = F(N, X)
   print(res)

   return 0

if __name__ == '__main__': main()

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

bagaAtsusas=[]
bagaAtsusasP=[]
def bagaAtsusa(number):
  if number==0:
    bagaAtsusas.append(1)
    return 1
  else:
    tmp=3+ bagaAtsusa(number-1)*2
    bagaAtsusas.append(tmp)
    return tmp

def bagaAtsusaP(number):
  if number==0:
    bagaAtsusasP.append(1)
    return 1
  else:
    tmp=1 + bagaAtsusaP(number-1)*2
    bagaAtsusasP.append(tmp)
    return tmp

#どのバーガーまであるのかを知りたい
def donoBaga(bagaLevel,fukasa,numList,ans):
  if(fukasa==1):
    numList[bagaLevel-1]=0
    #今までのを足せばわかる
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    print(ans)
  elif(fukasa<bagaAtsusas[bagaLevel-1]+1):
    #つぎへ
    numList[bagaLevel-1]=0
    fukasa=fukasa-1
    donoBaga(bagaLevel-1,fukasa,numList,ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]+1):
    numList[bagaLevel-1]=1
    #今までのを足せばわかる
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    print(ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]+2):
    numList[bagaLevel-1]=1
    #今までのを足せばわかる
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
  elif(fukasa<bagaAtsusas[bagaLevel-1]*2+2):
    #つぎへ
    numList[bagaLevel-1]=1
    fukasa=fukasa-(bagaAtsusas[bagaLevel-1]+2)
    ans=ans+1
    donoBaga(bagaLevel-1,fukasa,numList,ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]*2+2):
    numList[bagaLevel-1]=2
    #今までのを足せばわかる
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
  elif (fukasa==bagaAtsusas[bagaLevel-1]*2+3):
    numList[bagaLevel-1]=2
    #今までのを足せばわかる
    for i in range(bagaLevel-1,len(numList)):
      ans+=bagaAtsusasP[i]*numList[i]
    ans=ans+1
    print(ans)
    
bagaAtsusa(n)
bagaAtsusaP(n)
numList=[0]*n
ans=0
donoBaga(n,x,numList,ans)
#print(numList)
#print(bagaAtsusas)
#print(bagaAtsusasP)

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())
L2 = [1]
j = 1
for i in range(N+2):
    j *= 2
    L2.append(j)
Y = 0
for i in range(N+1):
    if L2[N+1-i] - 1 == X:
        Y += L2[N-i]
        print(Y)
        break
    elif L2[N+2-i] - 3 == X:
        Y += L2[N+1-i] - 1
        print(Y)
        break
    elif L2[N+1-i] - 1 < X:
        Y += L2[N-i]
        X -= L2[N+1-i] - 1
    else:
        X -= 1
else:
    print(Y)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
N,X = map(int,input().split())
def n_barg_hight(n):
	if(n == 0):
		return 1

	L1barg_height = n_barg_hight(n-1)
	Lbarg_height = 1 + L1barg_height + 1 + L1barg_height + 1
	return Lbarg_height

def n_barg_pat(n):
	if(n == 0):
		return 1
	L1barg_pat = n_barg_pat(n-1)
	Lbarg_pat = 1 + L1barg_pat*2
	return Lbarg_pat


def answer(N,X):

	if(X == 1):
		if(N == 0):
			return 1
		else:
			return 0
	
	elif(X == n_barg_hight(N)):
		return n_barg_pat(N)

	elif(X == n_barg_hight(N)//2 + 1):
		return n_barg_pat(N-1)+1

	elif(X <= n_barg_hight(N)//2):
		return answer(N-1,X-1)

	elif(X > n_barg_hight(N)//2 + 1):
		Lbarg = n_barg_pat(N-1) + answer(N-1,X-n_barg_hight(N-1)-2) +1
		return Lbarg


print(answer(N,X))

Submission status: Accepted

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

num = 1
pate = 1
for i in range(n):
    num = num * 2 + 3
    pate = pate * 2 + 1

def culc(l, idx, num, pate):
    npate = (pate - 1) // 2
    nnum = (num - 3) // 2
    mid = (num + 1) // 2
    if l == 1:
        if idx == 0:
            return 0
        elif idx == 1:
            return 0
        elif idx == 2:
            return 1
        elif idx == 3:
            return 2
        elif idx == 4:
            return 3
        else:
            return 3
    elif mid == idx:
        return npate + 1
    elif mid < idx:
        return npate + 1 + culc(l - 1, idx - mid, nnum, npate)
    else:
        return culc(l - 1, idx - 1, nnum, npate)
print(culc(n, x, num, pate))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
Z=[0]+[ 2**(i+2) -3 for i in range(N+1)]
B=[0]+[ 2**(i+1) -2 for i in range(N+1)]
P=[0]+[ 2**(i+1) -1 for i in range(N+1)]
ans=0
def arg(l,i):
    global ans
    if l != 0 :
        if Z[l]/2+1/2 < i :
            ans += (1 + P[l-1])
#            print("uga")
            return  arg( l-1 , i-( (Z[l]-1)/2 + 1 ) ) 

        elif Z[l]/2 +1/2  > i :
 #           print("aho")
            return arg( l-1 , i - 1)

        else :
            ans += P[l-1] + 1
        #    print("hoge")
    else :
        pass
arg(N+1,X)
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)

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

num = [0] * (n + 1)
num_p = [0] * (n + 1)
num_h = [0] * (n + 1)
num[0] = 1
num_p[0] = 1

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

for i in range(n + 1):
    num_h[i] = num[i] // 2 + 1

# idx 番目までに含むPの数を返す
def func(idx, n):
    if idx == 1 and n == 0:
        return 1
    if idx == 1 and n == 1:
        return 0
    if idx <= n or n < 0:
        return 0

    if idx == num_h[n]:
        ret = num_p[n - 1] + 1

    elif idx > num_h[n]:
        ret = num_p[n] - func(num[n] - idx - 1, n - 1)

    elif idx < num_h[n]:
        ret = func(idx - 1, n - 1)

    return ret

print(func(x, n))

Submission status: Accepted

Solution code:
n_x = input()
n_x_list =n_x.split(' ')

N = int(n_x_list[0])
X = int(n_x_list[1])

# g_list = [''] * N
# def G(N):
#     if N == 0:
#         return 'p'
#
#     gn_1 = G(N-1)
#
#     return 'b' + gn_1 + 'p' + gn_1 + 'b'

# g_n = G(N)
# print(g_n)
# eaten_burger = g_n[0:X]
# print(eaten_burger)
# ans = eaten_burger.count('p')
# print(ans)

def L(N):
    return 2 ** (N+2) - 3

def P(N):
    return 2 ** (N+1) - 1

def solve(N, X):
    half_l = int(L(N) / 2)
    if N == 0 and X >= 1:
        return 1
    elif N == 0 and X == 0:
        return 0

    if half_l <= 1:
        return 0
    elif X < half_l:
        return solve(N - 1, X - 1)
    elif X == half_l:
        return P(N-1)
    elif X == half_l + 1:
        return P(N-1) + 1
    elif half_l + 1 < X:
        return P(N-1) + 1 + solve(N-1, (X - L(N-1) - 2))
    elif half_l * 2 + 3 == X:
        return 2 * P(N-1) + 1


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

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
len_b=2**(n+2)-3
p=[2**(i+1)-1 for i in range(n)]
start=1
end=len_b
center=(end+1)//2
count1=0
count2=n-1
while True:
    if count2==-1:
        count1+=1
        break
    elif x==start:
        break
    elif x==center:
        count1+=p[count2]+1
        break
    elif x==end:
        count1+=p[count2]*2+1
        break
    elif x<center:
        start=start+1
        end=center-1
        center=(start+end)//2
        count2-=1
    else:
        start=center+1
        end=end-1
        center=(start+end)//2
        count1+=p[count2]+1
        count2-=1
print(count1)

Submission status: Accepted

Solution code:
n,k = map(int,input().split())
pk = [1]
pz = [1]
for i in range(n):
  pk.append(pk[-1]*2+1)
  pz.append(pz[-1]*2+3)
ans = 0
for i in range(n,-1,-1):
  z = pz.pop()
  ka = pk.pop()
  if k>= z//2:
    ans += ka//2
    k-=z//2
    if k:
      ans+=1
  if k:
    k-=1
print(ans)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[]
for i in range(n+1):
  l.append(2**(i+1)-1)
m=[]
for i in range(n+1):
  m.append(2**(i+2)-3)
c=0
for i in range(n,-1,-1):
  if x<2**(i+1)-1:
    x-=1
  elif x==2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    x=0
  elif x>2**(i+1)-1:
    if i!=0:
      c+=l[i-1]+1
    elif i==0:
      c+=1
    elif x==m[i]:
      x-=1
    x=x-(2**(i+1)-1)
print(c)

Submission status: Accepted

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

    n_layers_at_level = {0: 1}
    n_patties_at_level = {0: 1}
    for i in range(1, n):
        n_layers_at_level[i] = 2 * n_layers_at_level[i-1] + 3
        n_patties_at_level[i] = 2 * n_patties_at_level[i-1] + 1

    def amount_of_patties_from_bottom(level, n_layer):
        if level == 0:
            return 1

        lower_level_n_layer     = n_layers_at_level[level-1]
        lower_level_n_patties   = n_patties_at_level[level-1]
        mid_point = lower_level_n_layer + 2

        ret = 0
        if n_layer <= 1:
            ret = 0
        elif n_layer <= mid_point:
            if n_layer == mid_point:
                ret += 1
            ret += amount_of_patties_from_bottom(level - 1, n_layer - 1)
        else:
            ret += 1 + lower_level_n_patties
            ret += amount_of_patties_from_bottom(level - 1, n_layer - mid_point)
        return ret

    print(amount_of_patties_from_bottom(n, x))
    return


main()

Submission status: Accepted

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

al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx):
    if idx == 1:
        if x >= 5:
            return ans + 3
        if x <= 0:
            return ans
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
    return solve2(ans, x, idx - 1)


def solve():
    n, x = map(int, input().split())
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    print(solve2(0, x, n))


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

answer = 0
red = x

searching_index = n
while red > 0:
    for i in reversed(range(searching_index + 1)):
        length = 2**(i + 2) - 3
        if red >= length:
            if red >= length + 1:
                answer += 1
                red -= 1
            searching_index = i
            answer += 2**(i+1) - 1
            red -= length
            break
        red -= 1

print(answer)

Submission status: Accepted

Solution code:
def cnt(n, x):
	if x==0:
		return 0
	elif n==0:
		return 1
	elif x<2**(n+1)-1:
		return cnt(n-1, x-1)
	elif x==2**(n+1)-1:
		return 2**n
	elif x<2**(n+2)-3:
		return cnt(n-1, 2**(n+1)-3) + 1 + cnt(n-1, x-2**(n+1)+1)
	else:
		return 2**(n+1)-1

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

Submission status: Accepted

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

import math

al = [0, 5] + [0] * 49
bl = [0, 3] + [0] * 49


def solve2(ans, x, idx, cnt):
    if idx == 1:
        if x >= 5:
            return ans + 3
        return ans + (0, 0, 1, 2, 3, 3)[x]
    if x >= al[idx - 1] + 1:
        ans += bl[idx - 1]
        x -= al[idx - 1] + 1
        if x >= 1:
            ans += 1
            x -= 1
    else:
        x -= 1
        if x <= 0:
            return ans
    return solve2(ans, x, idx - 1, cnt)


def solve(n, x):
    for i in range(2, n + 1):
        al[i] = al[i - 1] * 2 + 3
        bl[i] = bl[i - 1] * 2 + 1
    ans = solve2(0, x, n, 0)
    print(ans)


if __name__ == "__main__":
    n, x = map(int, input().split())
    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):
    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, raw_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 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): # 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))