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 p_num(n,x):
    #print("_",n,x)

    m = 2**(n+1)-1
    #print("m",m,2*m-1)

    if n==0:
        return 1
    else:
        if x==1:
            return 0
        elif x==2*m-1:
            return m
            
        if x < m:
            #print("::1")
            return p_num(n-1, x-1)
        elif x > m:
            #print("::2")
            return (m-1)//2 + 1 + p_num(n-1, x-m)
        else:
            #print("::3")
            return (m-1)//2 + 1


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

print(p_num(n,x))

Submission status: Accepted

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

# (i)XがLバーガーの半分より上かどうか？を計算
# (ii-i)上の場合: sumに下半分のパティの数を加算。下半分を切り捨てて、L-1バーガに対して、
#        再度X = (X-(Lバーガーの半分の枚数))で(i)から計算
# (ii-ii)下の場合: 上半分を切り捨てて、L-1バーガに対して再度X = (X-(Lバーガーの半分の枚数))で(i)から計算

patty_num_map = {}
size_map = {}
patty_num_map[0] = 1
size_map[0] = 1
for i in range(1, 51):
    patty_num_map[i] = 1+patty_num_map[i-1]*2
    size_map[i] = 3+size_map[i-1]*2

L = N
patty_sum = 0
L1_map = {}
L1_map[0] = 0
L1_map[1] = 0
L1_map[2] = 1
L1_map[3] = 2
L1_map[4] = 3
L1_map[5] = 3
L1_map[6] = 3
for i in range(7, 10000):
    L1_map[i] = 3
while True:
    half = size_map[L]//2+1
    if L < 2:
        patty_sum += L1_map[X]
        break
    if X > half:
        patty_sum += patty_num_map[L-1]+1  # 真ん中のpattyの分
        # X -= half+1  # 一番上のバティの分
        X -= half
        L -= 1
    elif X < half:
        X -= 1  # 一番下のバンの分
        L -= 1
    else:  # ちょうど半分
        patty_sum += patty_num_map[L-1]+1
        break
print(patty_sum)

Submission status: Accepted

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

def left(total,x):
    if x > (total+1)//2:
        return x-(total+1)//2
    else:
        return x
def pati(n):
    return 2**(n+1)-1

n,x = map(int,input().split())
num = []
p = []
for i in range(n-1):
    num.append(total(i))
for i in range(n+1):
    p.append(pati(i))


one = ["B","P","P","P","B"]
num.reverse()
eat = [0 for i in range(n+1)]

ans = 0
for i in range(n-1):
    if x == total(n-i):
        eat[n-i] += 1
        x = 0
    elif x > (total(n-i)+1)//2:
        eat[n-i-1] += 1
        x = left(total(n-i),x)
        ans += 1
    elif x == (total(n-i)+1)//2:
        eat[n-i-1] += 1
        eat[0] += 1
        x = 0
    else:
        x -= 1

for i in range(len(eat)):
    ans += eat[i]*p[i]
if 2<=x<=4:
    ans += x-1
elif x == 5:
    ans += 3
print(ans)

Submission status: Accepted

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

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

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

def num_of_P_from_bottom(level, x):
    if level == 0:
        return 1

    prev_level_all = num_of_all[level-1]
    prev_level_P   = num_of_P[level-1]
    ret = 0

    if x <= 1:
        return 0
    elif x <= (2 + prev_level_all):
        if x == 2 + prev_level_all:
            ret += 1
        ret += num_of_P_from_bottom(level-1, x-1)
    else:
        ret += 1 + prev_level_P
        ret += num_of_P_from_bottom(level-1, x - (prev_level_all + 2))
    return ret

tmp = num_of_P_from_bottom(n, x)
print(tmp)

Submission status: Accepted

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

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

def count_p(level, X):
    if X == 0:
        return 0
    if X == burgersize[level]:
        return pnum[level]
    if level == 0:
        return 1
    Xmid = (burgersize[level] - 1) // 2 + 1
    if X < Xmid:
        return count_p(level - 1, X - 1)
    else:
        return pnum[level - 1] + 1 + count_p(level - 1, X - Xmid)

print(count_p(N, X))

Submission status: Accepted

Solution code:

N,X=[int(_) for _ in input().split()]
def countP(n):
    if n == 0:
        return 1
    elif n == 1:
        return 3
    else:
        return 1 + countP(n-1) * 2

def countBP(n):
    if n == 0:
        return 3
    elif n == 1:
        return 5
    else:
        return 3 + countBP(n-1) * 2

def countPinBP(n,x):
    if x == 1:
        return 0
    if n == 0:
        if x == 1:
            return 0
        else:
            return 1
    elif n == 1:
        if x == 1:
            return 0
        elif x < 5:
            return x - 1
        else:
            return 3
    else:
        #iH = countBP(n) // 2
        iH = 1 + countBP(n-1)
        if x <= iH:
            return countPinBP(n-1,x-1)
        elif x == iH + 1:
            return countP(n-1) + 1
        else:
            return countP(n-1) + 1 + countPinBP(n - 1, x - iH - 1)
print(countPinBP(N,X))

Submission status: Accepted

Solution code:
"""
P
1
B|P|P|P|B
0|1|1|1|0 3
B|BPPPB|P|BPPPB|B
0|3|1|3|0 7
a_1 = 1
a_n+1 = 2 * a_n + 3
b = 2b + 3 => b = -3
a_n + 3 = 4*2^(n-1)
a_n = 2^(n+2) - 3

b_1 = 1
b_n+1 = b_n * 2 + 1
c = 2c + 1 => c = -1
b_n + 1 = 2^n
b_n = 2^(n+1) - 1
"""


def check(n, x):
    if n == 0:
        return 0
    
    lower_n = 2 ** (n+1) - 3
    lower_pat = 2 ** n - 1
    if x == 1:
        return 0
    elif x == 1 + lower_n:
        return lower_pat
    elif x == 1 + lower_n + 1:
        return lower_pat + 1
    elif x == 1 + lower_n + 1 + lower_n:
        return lower_pat + 1 + lower_pat
    elif x == 1 + lower_n + 1 + lower_n + 1:
        return lower_pat + 1 + lower_pat
    elif 1 < x < 1 + lower_n:
        return check(n-1, x-1)
    elif 1 + lower_n + 1 <x< 1 + lower_n + 1 + lower_n:
        return lower_pat + 1 + check(n-1, x-1-lower_n-1)

N, X = [int(s) for s in input().split()]
print(check(N, X))

Submission status: Accepted

Solution code:
nx = list(map(int, input().split()))
n = nx[0]
x = nx[1]
p = 0
for i in range(n):
    l_thick = 2 ** (n - i + 1) - 3
    if x == 1:
        break
    elif x <= l_thick:
        x = x - 1
    elif x == l_thick + 1 :
        p += 2 ** (n - i) - 1
        break
    elif x <= l_thick * 2 + 1:
        x = x - l_thick - 2
        p += 2 ** (n - i)
    else:
        p += 2 * (2 ** (n - i) - 1) + 1
        break
print(p)

Submission status: Accepted

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


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


print(solve(N, X))

Submission status: Accepted

Solution code:
def dfs(lft, rgt, x, L):
    if x < lft: return 0
    if rgt <= x: return numPs[L]
    mid = (lft + rgt) // 2
    ans = 1 if mid <= x else 0
    ans += dfs(lft + 1, mid - 1, x, L - 1)
    ans += dfs(mid + 1, rgt - 1, x, L - 1)
    return ans

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

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

print(dfs(1, As[N], X, N))

Submission status: Accepted

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

def f(n):
    return 4 * pow(2, n) - 3
def g(n):
    return pow(2, n+1) - 1

def ss2(k, n):
    if n == 0:
        return 1
    nn = f(n)
    cc = (nn//2) + 1
    if k == 1:
        return 0
    if k >= nn:
        return g(n) 
    elif k == cc:
        return g(n-1) + 1  
    elif k > cc:
        return g(n-1) + 1 + ss2(k-cc, n-1)
    elif k < cc:
        return ss2(k-1, n-1)

print(ss2(X, N))

Submission status: Accepted

Solution code:
a,b= map(int,input().split())

l = 1

c = [1]
d = [1]

for i in range(50):
	c.append(2*c[-1]+3)
	d.append(2*d[-1]+1)
k = 0
while True:
	if a == 0:
		k += 1
		break
	elif b==1:
		break
	elif c[a] // 2 == b:
		k += d[a-1]
		break
	elif c[a] // 2 > b:
		a -= 1
		b -= 1
	elif c[a] // 2 + 1 == b:
		k += 1 + d[a-1]
		break
	elif c[a] // 2 + 1 < b and c[a] != b:
		a -= 1
		k += d[a]+1
		b -= c[a]+2
	else:
		k += d[a]
		break


print(k)

Submission status: Accepted

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

def solve():
    n, x = map(int, stdin.readline().split())
    items = []
    items.append([1,1])
    for i in range(1,n+1):
        items.append([items[-1][0]*2+3, items[-1][1]*2+1])
    
    if x<=n:
        print(0)
        return
    
    ans = 0
    p = n
    while p and x:
        half = (items[p][0]+1)//2
        if x>=half:
            ans += items[p-1][1] + 1
            x -= half
        else:
            x -= 1
        p -= 1

    if x:
        ans += 1
    print(ans)

solve()

Submission status: Accepted

Solution code:
def patti(level):
    return 2 ** (level + 1) - 1


def burger(level):
    return 2 ** (level + 2) - 3


def get_ans(level, x, num_patti):
    if level == 0:
        return num_patti + x

    if x == 1 or x == 0:
        return num_patti
    elif x < 1 + burger(level - 1):
        x -= 1
        return get_ans(level - 1, x, num_patti)
    elif x == 1 + burger(level - 1):
        return patti(level - 1) + num_patti
    elif x == 1 + burger(level - 1) + 1:
        return patti(level - 1) + num_patti + 1
    elif x < 1 + burger(level - 1) + 1 + burger(level - 1):
        x -= 1 + burger(level - 1) + 1
        num_patti += 1 + patti(level - 1)
        tmp = get_ans(level - 1, x, num_patti)
        return tmp
    else:
        return num_patti + patti(level - 1) * 2 + 1


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

print(get_ans(n, x, 0))

Submission status: Accepted

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

def p(n, x):
    if n == 0:
        return 1
    else:
        if x == 1:
            return 0
        elif x < (1 << n + 1) - 1:
            return p(n - 1, x - 1)
        elif x == (1 << n + 1) - 1:
            return 1 << n
        elif x < (1 << n + 2) - 3:
            return (1 << n) + p(n - 1, x - ((1 << n + 1) - 1))
        else:
            return (1 << n + 1) - 1

print(p(n, x))

Submission status: Accepted

Solution code:
layers = [1] * 51
patties = [1] * 51
for i in range(1, 51):
    layers[i] = 3 + layers[i-1] * 2
    patties[i] = 1 + patties[i-1] * 2


def count_patties(l, x):
    if l == 0 and x == 1:
        return 1
    if x <= 1:
        return 0
    y = layers[l-1]
    if x <= y+1:
        return count_patties(l-1, max(x-1, 0))
    else:
        return count_patties(l-1, min(x-y-2, y)) + patties[l-1] + 1


def main():
    N, X = map(int, input().split())
    print(count_patties(N, X))


if __name__ == "__main__":
    main()

Submission status: Accepted

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

plist = [1]
bplist = [1]

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

    bp = bplist[i] + 2 ** (i+2)
    bplist.append(bp)

ans = 0
index = n

while True:
    if index == 0:
        ans += 1
        break
    elif x > bplist[index-1] + 2:
        ans += plist[index - 1] + 1
        x -= bplist[index - 1] + 2
        index -= 1
    elif x == 1:
        break
    elif x == bplist[index-1] + 2:
        ans += plist[index-1] + 1
        break
    else:
        x -= 1
        index -= 1

print(ans)

Submission status: Accepted

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

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

def ans(m, y):
  if m == 0:
    return 1
  elif y == 1:
    return 0
  elif y < 2 ** (m + 1) - 1:
    return ans(m - 1, y - 1)
  elif y == 2 ** (m+1) -1:
    return pnum[m-1] + 1
  elif y != num[m]:
    r = y - (2 ** (m+1)-1)
    return pnum[m-1] + 1 + ans(m-1, r)
  else:
    return pnum[m]

print(ans(n, x))

Submission status: Accepted

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

def solve(n, x):

    if n == 0:
        return 1

    left = 1
    if x == left:
        return 0

    right = 2 ** (n + 2) - 3
    pivot = right // 2 + 1

    if x == right:
        return 1 + 2 * solve(n - 1, pivot - 2)

    if x < pivot:
        return solve(n - 1, x - 1)

    elif x == pivot:
        return 1 + solve(n - 1, pivot - 2)

    else:
        return solve(n - 1, pivot - 2) + 1 + solve(n - 1, x - pivot)




print(solve(N, X))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, X = map(int, input().split())
MEMO = {}


def f(n):
    if n in MEMO:
        return MEMO[n]
    if n == 0:
        return 1
    MEMO[n] = f(n - 1) * 2 + 3
    return MEMO[n]


MEMO2 = {}


def g(n, i):
    if i > f(n):
        i = f(n)
    if (n, i) in MEMO2:
        return MEMO2[(n, i)]
    if n == 0:
        return 1
    ans = 0
    if i > 1:
        ans += g(n - 1, i - 1)
    if i >= 1 + f(n - 1) + 1:
        ans += 1
    if i > 1 + f(n - 1) + 1:
        ans += g(n - 1, i - 1 - f(n - 1) - 1)
    MEMO2[(n, i)] = ans
    return ans


print(g(N, X))

Submission status: Accepted

Solution code:
nn,x=map(int,input().split())
ns=[1 for i in range(51)]
nm=[1 for i in range(51)]
for i in range(1,51):
    ns[i]=2*ns[i-1]+3
    nm[i]=2*nm[i-1]+1
def np(n,w):
    if w==0:
        return 0
    elif n==1:
        if w==1:
            return 0
        elif w==2:
             return 1
        elif w==3:
            return 2
        else:
            return 3
    else:
        if ns[n]//2+1>w:
            return np(n-1,w-1)
        elif ns[n]//2+1==w:
            return nm[n-1]+1
        else:
            return np(n-1,w-ns[n-1]-2)+nm[n-1]+1
print(np(nn,x))

Submission status: Accepted

Solution code:
def subsolve(n, x):
    if(n == 0 and x == 1):
        return 1
    if(x <= 1): # level 1
        return 0
    L1 = (1 << (n + 1)) - 3
    Ps = (1 << n) - 1
    if(x >= 2 * L1 + 2): # level 5
        return 2 * Ps + 1
    if(x > L1 + 2): #level 4
        return Ps + subsolve(n - 1, x - L1 - 2) + 1
    if(x == L1 + 2): # level  3
        return Ps + 1
    return subsolve(n - 1, x - 1) # level 2
if __name__ == '__main__':
    n, x = map(int, input().split())
    print(subsolve(n, x))

Submission status: Accepted

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

b = [1]
l = [1]
for i in range(n):
    b.append(b[-1]*2+1)
    l.append(l[-1]*2+3)

#print(*b)
#print(*l)

x -= 1
res = 0
lv = n
while lv >= 0:
    #print(x,lv,l[lv],b[lv],res)
    if lv == 0:
        res += 1
        break
    elif x <= 0:
        break
    elif x >= l[lv]-1:
        res += b[lv]
        break
    elif x == l[lv] // 2:
        res += b[lv-1] + 1
        break
    elif x > l[lv] // 2:
        res += b[lv-1] + 1
        lv -= 1
        x -= l[lv] + 2
    else:
        lv -= 1
        x -= 1
print(res)

Submission status: Accepted

Solution code:
import sys


def num_patty(level):
    return 2 ** (level + 1) - 1


def num_all(level):
    return 2 ** (level + 2) - 3


def total_patty(n, x):
    res = 0
    pos = x - 1
    for cur_level in range(n + 1)[::-1]:
        print("L = {}, P = {}, R = {}: ".format(cur_level, pos, res), file=sys.stderr, end="")
        if cur_level == 0:
            print("level zero", file=sys.stderr)
            res += 1
            break
        prev_level_total = num_all(cur_level - 1)
        cur_level_total = num_all(cur_level)
        if pos == 0:
            print("left bread", file=sys.stderr)
            break
        elif 1 <= pos <= prev_level_total:
            print("left block", file = sys.stderr)
            pos -= 1
            continue
        elif pos == prev_level_total + 1:
            print("middle patty", file = sys.stderr)
            res += num_patty(cur_level - 1) + 1
            return res
        elif prev_level_total + 2 <= pos <= cur_level_total - 2:
            print("right block", file = sys.stderr)
            res += num_patty(cur_level - 1) + 1
            pos -= prev_level_total + 2
            continue
        else:
            print("right bread", file = sys.stderr)
            res += num_patty(cur_level)
            break
    return res


def main():
    n, x = (int(z) for z in input().split())
    res = total_patty(n, x)
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def search(x,L,ans):
    if x<=1:
        return ans
    elif 1<x and x<=2**(L+1)-3:
        return search(x-1,L-1,ans)
    elif x==2**(L+1)-2:
        ans+=2**L-1
        return ans
    elif x==2**(L+1)-1:
        ans+=2**L
        return ans
    elif 2**(L+1)-1<x and x <= 2**(L+2)-5:
        ans+=2**L
        return search(x-2**(L+1)+1,L-1,ans)
    else:
        ans+=2**(L+1)-1
        return ans

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

ans=search(X,N,0)
print(ans)

Submission status: Accepted

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

f = [[0, 0] for i in range(N + 1)]

# 総数, パティ
f[0] = [1, 1]
for i in range(1, N + 1):
    # print(i)
    f[i][0] = 2 * f[i - 1][0] + 3
    f[i][1] = 2 * f[i - 1][1] + 1
    # print(f[i][0], f[i][1])

"""
for i in range(0, N + 1):
    print(f[i][0], f[i][1])
"""

leftA = 0
leftB = 0

ans = 0

for i in range(N, 0, -1):
    if leftA + 1 == X:
        # finish
        ans = leftB
        break
    elif leftA + 1 + f[i-1][0] == X:
        # finish
        ans = leftB + f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] > X:
        leftA = leftA + 1
    elif leftA + 1 + f[i-1][0] + 1 == X:
        # finish
        ans = leftB + 1 + f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] == X:
        # finish
        ans = leftB + 1 + 2 * f[i-1][1]
        break
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] > X:
        leftA = leftA + 1 + f[i-1][0] + 1
        leftB = leftB + 1 + f[i-1][1]
    elif leftA + 1 + f[i-1][0] + 1 + f[i-1][0] + 1 == X:
        # finish
        ans = leftB + 1 + 2 * f[i-1][1]
        break
    # print(leftA, leftB)

print(ans)

Submission status: Accepted

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

'''
N = 2
X = 7
'''

def ban(n):
	if n == 0:
		return 'P'
	return 'B'+ban(n-1)+'P'+ban(n-1)+'B'

def ans(n,x):
	if x <= 0:
		return 0
	if n == 0:
		return 1
	s = 2**(n+2) - 3
	a = (s-3)//2
	if x < 2+a:
		return ans(n-1,x-1)
	if x == 2+a:
		return ans(n-1,x-1)+1
	p = 2**(n)-1
	return p + 1+ans(n-1,x-2-a)

print(ans(N,X))

#ans = ban(N)[0:X]
#print(ans.count('P'))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))


N, X = inpl()

def main(N, X):
    B = [0]
    P = [1]
    T = [1]
    
    for i in range(50):
        b, p, t = B[-1], P[-1], T[-1]
        B.append(2*b + 2)
        P.append(2*p + 1)
        T.append(2*t + 3)
    
    ans = 0
    for n in range(N, 0, -1):
        if X <= T[n-1]:
            X -= 1
        elif X <= T[n-1] + 2:
            ans += P[n-1] + (X == T[n-1]+2)
            break
        elif X < 2*T[n-1] + 2:
            ans += P[n-1] + 1
            X -= (T[n-1] + 2)
        else:
            ans += 2*P[n-1] + 1
            break
    return ans

print(main(N, X))

Submission status: Accepted

Solution code:



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

f = [0] * (n+1)
g = [0] * (n+1)
f[0] = 1
g[0] = 1
for i in range(1, n+1):
    f[i] = f[i-1]* 2 + 3
    g[i] = g[i-1]* 2 + 1

total = 0
remain = x

def eat(n):

    global total
    global f
    global remain

    if remain == 0:
        return
    if n < 0:
        return
    if f[n] <= remain:
        total += g[n]
        remain -= f[n]
        return
    if f[n] > remain:
        remain -=1
        if remain == 0:
            return
        if f[n-1] > remain:
            eat(n-1)
        else:
            total += g[n-1]
            remain -= f[n-1]
            if remain == 0:
                return
            total += 1
            remain -= 1
            eat(n-1)

eat(n)
print(total)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
ans =0
while x > 0:
    if n==0:
        ans +=1
        break
    elif x == 1:
        break
    elif x >=2**(n+1)-1:
        ans += 2**n
        x -=2**(n+1)-1
        n -=1
    elif x == 2**(n+1)-2:
        ans += 2**n-1
        print(ans)
        exit()
    else:
        n -=1
        x -=1
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
A = [1] * 55
memo = {}


def func(n, x):
    if x <= 0:
        return 0
    if n == 0:
        return 1
    if (n, x) in memo:
        return memo[(n, x)]

    if x == 1:
        return 0
    if 1 < x <= 1 + A[n-1]:
        memo[(n, x)] = func(n-1, x-1)
        return memo[(n, x)]
    if x == 2 + A[n-1]:
        memo[(n, x)] = func(n-1, x-1) + 1
        return memo[(n, x)]
    if 2 + A[n-1] < x < A[n]:
        memo[(n, x)] = func(n-1, A[n-1]) + func(n-1, x-A[n-1]-2) + 1
        return memo[(n, x)]
    else:
        memo[(n, x)] = 2 * func(n-1, A[n-1]) + 1
        return memo[(n, x)]


def main():
    for i in range(1, N+1):
        A[i] = 2 * A[i-1] + 3

    print(func(N, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
a=[1]
b=[1]
for i in range(50):
    a.append(3+2*a[-1])
    b.append(1+2*b[-1])
def paty(n,x):
    if n==1:return 'bpppb'[-x:].count('p')
    if x==a[n]:return b[n]
    if x==1:return 0
    if x==a[n]//2+1: return b[n-1]+1
    if x<a[n]//2+1: return paty(n-1,x-1)
    if x>a[n]//2+1: return b[n-1]+1+paty(n-1,x-a[n]//2-1)
n,x=map(int, input().split())
print(paty(n,x))

Submission status: Accepted

Solution code:

def count(ps, N, X):
    if X ==0:
        return 0
    total = ps[N][0]
    #print("count N=%d, x=%-20d, total(N)=%d"%( N, X, total))
    half = (total +1)//2
    if X >= total:
        return ps[N][1]
    elif X < half:
        return count(ps, N-1,X-1)
    elif X == half:
        return ps[N-1][1] + 1
    elif X > half:
        return (ps[N-1][1] + 1) + count(ps, N-1, X - half)


def main(N,X):
    ps = [(1, 1)] # total, p
    for i in range(1, N+1):
        ps.append((ps[i-1][0] * 2 + 3, ps[i-1][1] * 2 + 1))

    c = count(ps, N, X)
    print(c)
    return c

#assert(main(2, 7)== 4)
#assert(main(1,1)==0)
#assert(main(50,4321098765432109)==2160549382716056)
N, X = (int(x) for x in input().split())
main(N, X)

Submission status: Accepted

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

l = [0 for i in range(N+1)]
l[0] = 1
p = [0 for i in range(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

x = X
d = N
ans = 0
while True:
    if x == 0:
        break
    if d == 0 and x != 0:
        ans += 1
        break

    m = (l[d]-1)//2
    if x < m:
        x = x - 1
    elif x == m:
        ans += p[d-1]
        break
    elif x > m:
        ans += p[d-1]+1
        x = x - (m+1)

    d -= 1

print(ans)

Submission status: Accepted

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

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

def count_p(level, X):
    if level == 0:
        return 1
    elif X == burgersize[level]:
        return pnum[level]
    elif X == 1:
        return 0
    elif X < (burgersize[level] - 1) // 2 + 1:
        return count_p(level - 1, X - 1)
    elif X == (burgersize[level] - 1) // 2 + 1:
        return pnum[level - 1] + 1
    elif X > (burgersize[level] - 1) // 2 + 1:
        return pnum[level - 1] + 1 + count_p(level - 1, X - (burgersize[level] - 1) // 2 - 1)
    return None

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

Submission status: Accepted

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

def length_burger(k):
	if k == 0:
		return(1)
	else:
		return(2*length_burger(k-1) + 3)

def num_pate(k, s):
	if s <= 0:
		return 0
	elif k == 0:
		return 1
	else:
		middle = length_burger(k) // 2 + 1
		if s < middle:
			return num_pate(k - 1, s - 1)
		elif s == middle:
			return num_pate(k - 1, s - 2) + 1
		else:
			if s == length_burger(k):
				return 2 * num_pate(k - 1, middle - 2) + 1
			else:
				return num_pate(k - 1, middle - 2) + 1 + num_pate(k - 1, s - middle)

print(num_pate(n, x))

Submission status: Accepted

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

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

ans = 0
for i in reversed(range(N)):
    if i > 0:
        if X == s[i]+2:
            ans += p[i]+1
            break
        elif X < s[i]+2:
            X -= 1
        else:
            X -= (s[i]+2)
            ans += p[i]+1
    else:
        ans += max(0,min(3, X-1))
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 9)

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

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


def dfs(kk, ss, tt):
    if ss > tt:
        return 0

    if kk == 0:
        return 1

    target_length = get_length[kk]
    m = (1 + target_length) // 2

    if 1 <= ss <= 2 and target_length - 1 <= tt <= target_length:
        return get_p[kk]

    if ss == 1:
        return dfs(kk, 2, tt)

    if tt == target_length:
        return dfs(kk, ss, tt - 1)

    if ss == m:
        return 1 + dfs(kk, ss + 1, tt)

    if tt == m:
        return dfs(kk, ss, tt - 1) + 1

    if ss < m < tt:
        return dfs(kk, ss, m - 1) + 1 + dfs(kk, m + 1, tt)

    if ss < m:
        return dfs(kk - 1, ss - 1, tt - 1)
    else:  # ss > m
        return dfs(kk - 1, ss - m, tt - m)


n, x = map(int, input().split())
ans = 0
if get_length[n] < 2 * x:
    ans = get_p[n] - dfs(n, 1, get_length[n] - x)
else:
    ans = dfs(n, 1, x)
print(ans)

Submission status: Accepted

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

memo = dict()
size = [0] * (n+1)
size[0] = 1

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

def dfs(i):
    global x
    res = 0
    if x <= 0:
        return 0
    if size[i] <= x and i in memo:
        x -= size[i]
        return memo[i]
    if i == 0:
        x -= 1
        return 1
    x -= 1 #B
    res += dfs(i-1)
    x -= 1 #P
    if x < 0:
        return res
    res += 1 #P
    res += dfs(i-1)
    x -= 1 #B
    memo[i] = res
    return res


print(dfs(n))

Submission status: Accepted

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

memol = {0: 1}
memop = {0: 1}


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

ret = 0
ln = 0
for i in range(n, -1, -1):
    if ln >= x:
        break
    ln += 1
    if ln >= x:
        break
    if ln + memol[i-1] > x:
        continue
    ln += memol[i-1]
    ret += memop[i-1]
    if ln == x:
        break
    ln += 1
    ret += 1
    if ln + memol[i-1] > x:
        continue
    ln += memol[i-1]
    ret += memop[i-1]
    if ln == x:
        break
    ln += 1

print(ret)

Submission status: Accepted

Solution code:
def func(N, X):
	global l, p

	if l[N] == X:
		return p[N]
	
	if X == 1:
		return 0
	temp = 1 + l[N - 1]
	s = 0
	if X <= temp:
		return func(N - 1, X - 1)
	temp += 1
	if X == temp:
		return p[N - 1] + 1
	temp += l[N - 1]
	if X <= temp:
		return func(N - 1, X - 2 - l[N - 1]) + p[N - 1] + 1
	return 2 * p[N - 1] + 1
	
		
N, X = map(int, input().split())

l = [0] * (N + 1)
p = [0] * (N + 1)

l[0] = 1
p[0] = 1

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

ans = func(N, X)

print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split(' '))
length = [1]
patty = [1]
p_before = 1
before = 1
for i in range(N):
    before = before*2+3
    length.append(before)
    p_before = 2*p_before+1
    patty.append(p_before)

def search(n,i):
    if i==0:
        return 1
    if 1<n<length[i-1]+2:
        return search(n-1, i-1)
    elif length[i-1]+2<n<2*length[i-1]+3:
        return patty[i-1]+1+search(n-2-length[i-1],i-1)
    elif n == 1:
        return 0
    elif n ==length[i-1]+2:
        return patty[i-1]+1
    elif n == 2*length[i-1]+3:
        return 2*patty[i-1]+1

print(search(X,N))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
B = [0] * (N + 1)
P = [1] * (N + 1)
for i in range(N):
  B[i + 1] = 2 * B[i] + 2
  P[i + 1] = 2 * P[i] + 1
S = [B[i] + P[i] for i in range(N + 1)]
cnt = 0
def burg(L, X):
  cnt = 0
  if X <= L:
    return 0
  if L == 0:
    return 1
  if X <= S[L - 1] + 1:
    return burg(L - 1, X - 1)
  if X == S[L]:
    return P[L]
  else:
    return P[L - 1] + 1 + burg(L - 1, X - S[L - 1] - 2)
print(burg(N, X))

Submission status: Accepted

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

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

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

Submission status: Accepted

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


def count(n, x):
    if [n, x] == [0, 1]:
        return 1
    elif x == 1:
        return 0
    elif x < 2 * 2 ** n - 1:
        return count(n - 1, x - 1)
    elif x == 2 * 2 ** n - 1:
        return count(n - 1, 2 * 2 ** n - 3) + 1
    elif x < 4 * 2 ** n - 3:
        return count(n - 1, 2 * 2 ** n - 3) + 1 + \
            count(n - 1, x - 2 * 2 ** n + 1)
    else:
        return 2 * count(n - 1, 2 * 2 ** n - 3) + 1


print(count(N, X))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def LBp(N,X,dLB):
    if N == 0 and X == 1:
        P = 1
    elif N >= 1:
        if X == 1:
            P = 0
        elif 2 <= X <= dLB[N-1]+1:
            P = LBp(N-1,X-1,dLB)
        elif X == dLB[N-1]+2:
            P = LBp(N-1,dLB[N-1],dLB) + 1
        elif dLB[N-1]+3 <= X <= dLB[N]-1:
            P = LBp(N-1,dLB[N-1],dLB) + LBp(N-1,X-dLB[N-1]-2,dLB) + 1
        elif X == dLB[N]:
            P = 2*LBp(N-1,dLB[N-1],dLB) + 1
    return P

def solve():
    N, X = map(int, input().split())
    dLB = [1]
    for i in range(1,N+1):
        dLB[i:] = [2*dLB[i-1]+3]
    res = LBp(N,X,dLB)
    return str(res)

if __name__ == '__main__':
    print(solve())