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

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

ans = 0
while 0<X:
    if(X<((HforL[N]-3)/2)+1):
        X -= 1
        N -= 1
        continue
    if(X==((HforL[N]-3)/2+1)):
        ans+=PforL[N-1]
        break
    if(X==((HforL[N]-3)/2+2)):
        ans+=PforL[N-1]+1
        break
    if(X<HforL[N]-1):
        ans += PforL[N-1]+1
        X -= 2+HforL[N-1]
        N -= 1
        continue
    if(X<=HforL[N]):
        ans += PforL[N]
        break
print(ans)

Submission status: Accepted

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

#a[i]:leveru i no sousuuuuu
a = [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]
#b[i]:leveru i no P sousuuuu
b = [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]


#レベルkのバーがーをしたからx枚食べたときのP
def f(k,x,a,b):
    if x == 0:
        return 0
    elif k == 0:
        return 1
    elif k== 1:
        if x <= 4:
            return x-1
        else:
            return 3
    else:
        if x == (a[k]-1)//2+1:
            return b[k-1] + 1
        elif x < (a[k]-1)//2+1:
            if x <= k:
                return 0
            else:
                return f(k-1,x-1,a,b)
        elif x >= a[k]-k:
            return b[k]
        else:
            return b[k-1] + f(k-1,x-(a[k]-1)//2-1,a,b) + 1

print(f(n,x,a,b))

Submission status: Accepted

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

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

res = 0
while n >= 0:
    if n == 0:                 # レベル1のバーガーはこれ以上細分化できない
        res += 1
        break
    elif x == 0:               # 左端
        break
    elif x == l[n] - 1:        # 右端
        res += p[n]
        break
    elif x == l[n] // 2:       # 中心
        res += p[n-1] + 1
        break
    elif x > l[n] // 2:        # 1個包含している
        res += p[n-1] + 1
        x -= l[n-1] + 2
        n -= 1
    else:                      # 包含していない
        n -= 1
        x -= 1

print(res)

Submission status: Accepted

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

p = [0 for _ in range(N+1)]
b = [0 for _ in range(N+1)]
t = [0 for _ in range(N+1)]
p[0] = 1
t[0] = 1
idx = 0
for i in range(1,N+1):
    p[i] = p[i-1]*2 + 1
    b[i] = b[i-1]*2 + 2
    t[i] = p[i]+b[i]
    if X == t[i]:
        print(p[i])
        exit()
    if t[i-1] < X < t[i]:
        idx = i

if X <= N:
    print(0)
    exit()

start = X
ans = 0
for i in reversed(range(1,N+1)):
    if t[i] - i <= start <= t[i]:
        ans += p[i]
        print(ans)
        exit()

    if t[i]//2 == start:
        ans += p[i-1]
        print(ans)
        exit()

    if t[i]//2 + 1 == start:
        ans += p[i-1] + 1
        print(ans)
        exit()

    if t[i]//2 + 1 < start < t[i] - i:
        ans += p[i-1] + 1
        start = start - t[i-1] - 2
    else:
        start = start - 1

print(ans)

Submission status: Accepted

Solution code:
import sys
def qwe(n,x,ans):
    n1 = "BPPPB"
    n2 = "BBPPPBPBPPPBB"
    if n==1:
        for s in n1:
            if s=="P": ans+=1
            x-=1
            if x==0:
                print(ans)
                sys.exit()
    else:
        for s in n2:
            if s=="P": ans+=1
            x-=1
            if x==0:
                print(ans)
                sys.exit()

def main():
    n,x = map(int, input().split())
    if n<=2:
        qwe(n,x,0)
    a = [1]
    b = [1]
    for i in range(n-1):
        a.append(2*a[-1]+3)
        b.append(2*b[-1]+1)
    ans = 0
    if x== 2*a[n-1]+3:
        print(2*b[n-1]+1)
        sys.exit()
    elif x==2*a[n-1]+2:
        print(2*b[n-1]+1)
        sys.exit()
    elif x == a[n-1]+2:
        print(b[n-1]+1)
        sys.exit()
    elif x== a[n-1]+1:
        print(b[n-1])
        sys.exit()
    elif x > a[n-1]+2:
        ans += b[n-1]+1
        x -= a[n-1]+2
        n = n-1
    else:
        x -=1
        n = n-1
    while n>2 or x > 0:
        if x== 2*a[n-1]+3:
            ans += 2*b[n-1]+1
            print(ans)
            sys.exit()
        elif x==2*a[n-1]+2:
            ans += 2*b[n-1]+1
            print(ans)
            sys.exit()
        if x == a[n-1]+2:
            ans += b[n-1]+1
            print(ans)
            sys.exit()
        elif x== a[n-1]+1:
            ans+=b[n-1]
            print(ans)
            sys.exit()
        elif x > a[n-1]+2:
            ans += b[n-1]+1
            x -= a[n-1]+2
            n = n-1
        else:
            x -=1
            n = n-1
    if x==0:
        print(ans)
        sys.exit()
    qwe(n,x,ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
lens=[1 for _ in range(51)]
nump=[1 for _ in range(51)]
for i in range(50):
    lens[i+1]=2*lens[i]+3
    nump[i+1]=2*nump[i]+1
def level(n):
    return max(lvl for lvl,ln in enumerate(lens) if ln<=n)

def calc():
    table={}
    def _calc(l,x):
        if x==0:
            return 0
        if (l,x) in table:
            return table[(l,x)]
        if x==lens[l]:
            res=nump[l]
        elif x<=lens[l-1]:
            res=_calc(l-1,x-1)
        elif x==lens[l-1]+1:
            res=nump[l-1]
        elif x==lens[l-1]+2:
            res=nump[l-1]+1
        else:
            res=nump[l-1]+1+_calc(l-1,x-lens[l-1]-2)
        table[(l,x)]=res
        return res
    return _calc
whole=calc()
print(whole(*map(int,input().split())))

Submission status: Accepted

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

cnt = [0,1]
tmp = [[0,1]]

for i in range(n):

    tmp.append([cnt[0] * 2 + 2,cnt[1] * 2 + 1])
    cnt[0] = cnt[0] * 2 + 2
    cnt[1] = cnt[1] * 2 + 1

"""
半分に区切ってジャスト半分なら前の分+1を出力
大きければ前の分+1を足して次
小さければ数える数を1小さくしてレベルを下げる
"""
num = 0
for i in range(n,0,-1):
    if (sum(tmp[i])+1)/2 == k:
        num += tmp[i-1][1]+1
        break
    elif (sum(tmp[i])-1)/2 == k:
        num += tmp[i-1][1]
        break
    elif sum(tmp[i]) == k or sum(tmp[i])-1 == k:
        num += tmp[i][1]
        break
    elif (sum(tmp[i])-1)/2 < k:
        num += tmp[i-1][1]+1
        k = k - sum(tmp[i-1]) - 2
    elif (sum(tmp[i])-1)/2 > k:
        k = k - 1
print(num)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
pcnt = [0] * (N+1)
fcnt = [0] * (N+1)
pcnt[0] = fcnt[0] = 1
for i in range(N):
	pcnt[i+1] = pcnt[i]*2+1
	fcnt[i+1] = fcnt[i]*2+3

def func(l=N, x=X):
	if (l == 0):
		if (x >= 1):
			return 1
		else:
			return 0
	if (x < fcnt[l-1]+2):
		return func(l-1, x-1)
	else:
		return pcnt[l-1]+1+func(l-1, x-fcnt[l-1]-2)

print(func())

Submission status: Accepted

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


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


def count(N, X):
    if N == 0:
        return 1
    elif X <= N:
        return 0
    elif X >= PAndB(N) - (N - 1):
        return allPatty(N)
    elif X == PAndB(N - 1) + 2:
        return allPatty(N - 1) + 1
    elif X <= PAndB(N - 1) + 1:
        return count(N - 1, X - 1)
    else:
        return allPatty(N - 1) + 1 + count(N - 1, X - (PAndB(N - 1) + 2))


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,X = (int(i) for i in input().split(' '))
 
L = [1]
P = [1]
for i in range(N):
    L.append(2*L[i] + 3) # 総枚数
    P.append(2*P[i] + 1) # パティ数
 
# print(L)
# print(P)

# レベルlv バーガのx層目までにパティは何枚あるか？
def find_level(lv, x):
    
#    print(lv, x)
    if lv == 0:
        return 1
    # lvレベルバーガの真ん中の層
    midlv = L[lv-1] + 2
    
    # 最上層
    if x == L[lv]:
#        print('最上層')
        ret = P[lv]
    # 最上層から真ん中
    elif x < L[lv] and x > midlv:
#        print('最上層〜真ん中')
        ret = find_level(lv-1,x - midlv) + 1 + P[lv-1]
    # ちょうど真ん中
    elif x == midlv:
#        print('真ん中')
        ret = 1 + P[lv-1] 
    # 真ん中〜最下層
    elif x < midlv and x > 1:
#        print('真ん中〜最下層')
        ret = find_level(lv-1, x - 1)
    # 最下層
    else:
#        print('最下層')
        ret = 0
        
    return(ret)

r = find_level(N, X)
print(r)

Submission status: Accepted

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

table_l = [-1 for _ in range(51)]
table_p = [-1 for _ in range(51)]
table_l[0] = 1
table_p[0] = 1

for i in range(1, 51):
    table_l[i] = table_l[i-1] * 2 + 3
    table_p[i] = table_p[i-1] * 2 + 1


def f(level, x):
    if level == 1:
        if x == 0 or x == 1:
            return 0
        if x == 2:
            return 1
        if x == 3:
            return 2
        else:
            return 3

    if table_l[level] == x:
        return table_p[level]

    if x - 1 <= table_l[level - 1]:
        return f(level - 1, x - 1)

    if x - 2 == table_l[level - 1]:
        return table_p[level - 1] + 1
    if x - 2 > table_l[level - 1]:
        xx = x - 2 - table_l[level - 1]
        return table_p[level - 1] + 1 + f(level - 1, xx)


print(f(n, x))

Submission status: Accepted

Solution code:
def main():
    """
    input:
        1 <= N <= 50
        1 <= X <= レベル N バーガーの層の総数

    レベル L バーガー
        バン 1枚
        レベル L−1バーガー
        パティ 1枚
        レベル L−1バーガー
        バン 1枚
    この順に下から積み重ねたもの

    output:
        N! の約数のうち、七五数 は何個
        七五数とは約数をちょうど 75個持つ正の整数
    """
    N, X = map(int, input().split())

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


def layers(N):
    layer = [0] * (N + 1)
    layer[0] = 1
    p_layer = [0] * (N + 1)
    p_layer[0] = 1

    for i in range(1, N+1):
        layer[i] = 1 + layer[i-1] + 1 + layer[i-1] + 1
        p_layer[i] = p_layer[i-1] + 1 + p_layer[i-1]

    return layer, p_layer


def f(N, X):
    """
    差分は4から始まって2倍になる
    2^32 < layer 50 < 2^64

    下からX層を食べるので端から考える
    """
    layer, p_layer = layers(N)

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

        ans = 0
        # L下のバン
        if X >= 1:
            X -= 1
            # print("L下", N, X, ans)
            if X >= layer[N-1]:
                X -= layer[N-1]
                ans += p_layer[N-1]
                # print("L-1下バーガー", N, X, ans)
                if X >= 1:
                    X -= 1
                    ans += 1
                    # print("Lパティ", N, X, ans)
                    if X >= layer[N-1]:
                        X -= layer[N-1]
                        ans += p_layer[N-1]
                        # print("L-1上バーガー", N, X, ans)
                    else:
                        ans += patty(N-1, X)
            else:
                ans += patty(N-1, X)

        return ans

    ans = patty(N, X)
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
pcnt = [0] * (N+1)
fcnt = [0] * (N+1)
pcnt[0] = fcnt[0] = 1
for i in range(N):
	pcnt[i+1] = pcnt[i]*2+1
	fcnt[i+1] = fcnt[i]*2+3

def func(l=N, x=X):
	if (l == 0):
		if (x >= 1):
			return 1
		else:
			return 0
	if (x <= 1):
		return 0
	if (x < fcnt[l-1]+2):
		return func(l-1, x-1)
	elif (x == fcnt[l - 1] + 2):
		return pcnt[l-1]+1
	else:
		return pcnt[l-1]+1+func(l-1, x-fcnt[l-1]-2)

print(func())

Submission status: Accepted

Solution code:
class Burg:
    def __init__(self):
        self.lv = [2**(i+1) - 1 for i in range(51)]

    def make_burg(self, n, m):
        if n == 0:
            return 1, m - 1
        num = 4 * 2**n - 3
        if num <= m:
            return self.lv[n], m - num
        if m <= 1:
            return 0, 0
        a, b = self.make_burg(n - 1, m - 1)
        if b <= 1:
            return a + b, 0
        c, d = self.make_burg(n - 1, b - 1)
        return a + c + 1, max(0, d - 1)

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

gen = Burg()
print(gen.make_burg(n, x)[0])

Submission status: Accepted

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

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

def lune(n,x):
    if n == 0 and x > 0:
        return 1
    for i in range(1,n+1):
        if x > h(n-i) + i:
            return (p(n-i) + 1 + lune(n-i, x - (h(n-i) + i) - 1))
    if x > n:
        return 1
    else:
        return 0

def main():
    n,x = map(int, input().split())
    if x >= (h(n) + 1) // 2:
        print(p(n) - lune(n, h(n) - x))
    else:
        print(lune(n,x))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

import math

def Pn(n):
    x = 0
    for i in range(n):
        x = x + 2**i
        yield x

Paty = list(Pn(N+1))
Bager = [2*i -1 for i in Paty]

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

    harf = (Bager[n] + 1) // 2

    if x == harf:
        return 1 + Paty[n-1]

    if x > harf:
        return Ln(n-1, x - 2 - Bager[n-1]) + Paty[n-1] + 1
    else:
        return Ln(n-1, x-1)

print(Ln(N, X))

Submission status: Accepted

Solution code:
import math

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
 
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)
 

def f(b,n):
	if n < b:
		return n
	return f(b, n//b) + n%b
 
N,X = map(int,input().split())
X-=1

P = [0,1]

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

left = 0
right = 1
for i in range(N):
    right = right*2 + 3

mid = int((right-left)/2)
ans = 0

while(left <= right):
    if(X<mid):
        right = mid-1
        left += 1
        N-=1
    elif (X>mid):
        left = mid+1
        right -= 1
        ans = ans + P[N] + 1
        N-=1
    else:
        ans = ans + P[N] + 1
        break

    mid = left+int((right-left)/2)
    
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def print_and_exit(X, eated_P):
    if X == 0:
        print eated_P
        exit()

table = {}

def get_burger_size(L):
    global table
    if L in table:
        return table[L]
    if L == 0:
        table[0] = (1L, 1L)
        return (1L, 1L)

    l_1_burger = get_burger_size(L - 1)
    table[L - 1] = l_1_burger
    return  (3L + 2L * l_1_burger[0], 1L + 2L * l_1_burger[1])

g_eated = 0
g_eated_P = 0

def calc_eated(X, L, eated_P):
    X -= 1
    print_and_exit(X, eated_P)

    (eated_f, eated_P_f) = get_burger_size(L - 1)
    if X < eated_f:
        calc_eated(X, L - 1, eated_P)
    X -= eated_f
    eated_P += eated_P_f
    print_and_exit(X, eated_P)

    eated_P += 1
    X -= 1
    print_and_exit(X, eated_P)

    (eated_f, eated_P_f) = get_burger_size(L - 1)
    if X < eated_f:
        calc_eated(X, L - 1, eated_P)
    X -= eated_f
    eated_P += eated_P_f
    print_and_exit(X, eated_P)

    X -= 1
    print_and_exit(X, eated_P)



def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, X] = [long(input_raw[0]), long(input_raw[1])]
    calc_eated(X, N, 0)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
i = n
jouken = False
while True:
    if i == 0:
        if x ==1:
            ans += 1
        break
    if x==1:
        break
    if x == su[i]:
        ans+=a[i]
        break
    if x == int(su[i]/2) +1:
        ans += a[i-1] +1
        break
    elif x < int(su[i]/2)+1:
        i -= 1
        x -= 1
    elif x > int(su[i]/2)+1:
        i -= 1
        ans += a[i]+1
        x -= su[i]
        x -= 2

print(ans)

Submission status: Accepted

Solution code:
#coding:utf-8
ls_len = [1]
ls_p = [1]
for i in range(50):
    ls_len.append(2*ls_len[-1]+3)
    ls_p.append(1+2*ls_p[-1])
n,x = map(int,input().split())

def calc_p(level,x):
    if level == 0:
        return 1
    elif x == ls_len[level]-1:
        return ls_p[level]
    elif x == 0:
        return 0
    elif x == (ls_len[level]-1)/2:
        return ls_p[level-1]+1
    elif x < (ls_len[level]-1)/2:
        return calc_p(level-1,x-1)
    else:
        return calc_p(level-1,x-2-ls_len[level-1])+ls_p[level-1]+1
print (calc_p(n,x-1))

Submission status: Accepted

Solution code:
l = [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]
p = [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]

n, x = [int(i) for i in input().split()]
h = l[n]
e = 0
for i in range(n)[::-1]:
    if x >= 1 :
        x -= 1
    else:
        break
    if x >= l[i]:
        x -= l[i]
        e += p[i]
    else:
        continue
    if x >= 1 :
        x -= 1
        e += 1
    else:
        break
    if x >= l[i]:
        x -= l[i]
        e += p[i]
    else:
        continue
print(e)

Submission status: Accepted

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

pl = [1]
pa = [1]

for i in range(n):
    tmpp = pl[-1]
    tmpa = pa[-1]
    pl.append(tmpp*2+1)
    pa.append(tmpa*2+3)

def largest(n,x):
    if x <= 0:
        return 0
    else:
        if n <= 0:
            if x >= 4:
                return 3
            else:
                return x
        else:
            if x > pa[n]:
                return pl[n] + 1 + largest(n-1, x-2-pa[n])
            elif x == pa[n]:
                return pl[n]
            else:
                return largest(n-1,x-1)

print(largest(n,x))

Submission status: Accepted

Solution code:
N,X = map(int,input().split())
def lb(N):
    if N != 0:
        return 2*lb(N-1)+3
    else:
        return 1
def pn(N):
    if N != 0:
        return 2*pn(N-1)+1
    else:
        return 1
def B(N,X):
    if X == 0:
        return 0
    elif N == 0:
      	return 1
    elif lb(N-1)+1 >= X:
        return B(N-1,X-1)
    else:
        return pn(N-1)+1+B(N-1,X-lb(N-1)-2)
print(B(N,X))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
def all_putty(m):
 return 2**(m+1)-1
count = 0
for l in range(n+1)[::-1]:
  mark = 2**(1+l)-1
  if x >= mark:
    count += all_putty(l-1) +1
    x -= mark
  else:
    x -= 1
print(count)

Submission status: Accepted

Solution code:
# encoding: utf-8
N, X = map(int, input().split())

def count(level, pos):
    L_child = 2 ** ((level - 1) + 2) - 3
    P_child = 2 ** ((level - 1) + 1) - 1
    # solved
    if pos == 0: return 0 if level > 0 else 1
    elif pos < L_child + 1: return count(level - 1, pos - 1)
    elif pos == L_child + 1: return P_child + 1
    elif L_child + 1 < pos < 2 * (L_child + 1):
        return P_child + 1 + count(level - 1, pos - (L_child + 2))
    else: return 2 * P_child + 1

print(count(N, X - 1))

Submission status: Accepted

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

burger = [1]
pati = [1]
for i in range(1,52):
    burger.append(burger[i-1]*2+3)
    pati.append(pati[i-1]*2+1)
    
def calc(l, eat):
    if l == 0:
        return 1
    elif eat == 1:
        return 0
    elif eat <= burger[l-1]+1:
        return calc(l-1, eat-1)
    elif eat == burger[l-1]+2:
        return pati[l-1] + 1
    elif eat <= (burger[l-1]+1)*2:
        return calc(l-1, eat-(2+burger[l-1])) + pati[l-1] + 1
    elif eat == (burger[l-1]*2) + 3:
        return (2*pati[l-1]) + 1

print(calc(N, X))

Submission status: Accepted

Solution code:
import numpy as np
def niku(level, num):
	maisu = 2**(level+2)-3
	if(num <= level):
		return 0
	elif(level == 0):
		return 1
	elif(num < (maisu+1)/2):
		return niku(level-1, num-1)
	elif(num == (maisu+1)/2):
		return 2**(level+1-1)-1+1
	else:
		return 2**(level+1-1)-1+1+niku(level-1, num-((maisu+1)/2))

def main():
	
	buf = input().split()
	n = int(buf[0])
	x = int(buf[1])
	print(niku(n, x))
		
main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
n,x=[int(x) for x in input().split()]
burgurnum=["" for _ in [0]*51]
burgurnumP=["" for _ in [0]*51]
def burgurNumFunc(level):
    if burgurnum[level]=="":
        if level==0:
            burgurnum[level]=1
        else:
            burgurnum[level]=burgurNumFunc(level-1)*2+3
    return burgurnum[level]
def burgurnumPFunc(level):
    if burgurnumP[level]=="":
        if level==0:
            burgurnumP[level]=1
        else:
            burgurnumP[level]=burgurnumPFunc(level-1)*2+1
    return burgurnumP[level]
    
    
def burger(num,level):
    if level==0:
        return 1
    elif num==1:
        return 0
    elif 1<num<=1+burgurNumFunc(level-1):
        return burger(num-1,level-1)
    elif num==burgurNumFunc(level-1)+2:
        return burgurnumPFunc(level-1)+1
    elif burgurNumFunc(level-1)+2<num<=burgurNumFunc(level-1)*2+2-1:
        return burgurnumPFunc(level-1)+1+burger(num - burgurNumFunc(level-1)-2,level-1)
    else:
        return burgurnumPFunc(level-1)*2+1
    

print(burger(x,n))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
bli = []
pli = []
z = 2 ** (n + 2) - 3
count = 0
for i in range(n + 1):
    y = 2 ** (i + 2) - 3
    bli.append(y // 2 + 1)
    pli.append(y // 2)
for i in range(n, -1, -1):
    if x == 0:
        break
    elif i == 0:
        count += 1
        break
    elif x > (2 ** (i + 2) - 3) // 2 + 1:
        count += bli[i - 1] + 1
        x -= (2 ** (i + 2) - 3) // 2
    elif x == (2 ** (i + 2) - 3) // 2 + 1:
        count += bli[i - 1] + 1
        break
    x -= 1
print(count)

Submission status: Accepted

Solution code:
def abc115_d():
    n, x = map(int, input().split())
    l = [1] * 51
    p = [1] * 51
    for i in range(50):
        l[i + 1] = 2 * l[i] + 3
        p[i + 1] = p[i] * 2 + 1

    ans = 0
    while n:
        if x == l[n]:
            ans += p[n]
            break
        elif x > (l[n] // 2):
            ans += p[n - 1] + 1
            x -= (l[n - 1] + 2)
            n -= 1
        else:
            x -= 1
            n -= 1
    if x == 1:
        ans += 1

    print(ans)


abc115_d()

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
bg=[1]
l=[1]
for _ in range(N):
    bg.append(bg[-1]*2+1)
    l.append(l[-1]*2+3)

def eat(n,x):#レベル,食べる層の数
    if x<=1: return 0
    if x==l[n-1]+1: return bg[n-1]
    if x==l[n] or x==l[n]-1: return bg[n]
    if x<=l[n-1]: return eat(n-1,x-1)
    return bg[n-1]+1+eat(n-1,x-l[n-1]-2)
print(eat(N,X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
memo = {}


def solve(N, X):
    if (N, X) not in memo:
        l = (pow(2, N + 2) - 3)
        l2 = (l - 3) // 2 + 1
        if N == 0:
            return 1
        if X == 1:
            return 0
        elif X <= l2:
            memo[(N, X)] = solve(N - 1, X - 1)
        elif X == l2 + 1:
            memo[(N, X)] = solve(N - 1, l2 - 1) + 1
        elif X < l:
            left = solve(N - 1, l2 - 1)
            right = solve(N - 1, X - 1 - l2)
            memo[(N, X)] = left + 1 + right
        elif X == l:
            memo[(N, X)] = solve(N - 1, l2 - 1) * 2 + 1
    return memo[(N, X)]


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

Submission status: Accepted

Solution code:
import pdb

def eat(n, x):
    ret = 0

    if x == 0:
        return 0, x

    if n == 0:
        x -= 1
        return 1, x

    if allnum[n] <= x:
        x -= allnum[n]
        return pnum[n], x
        
    # eat bread
    x -= 1 
    if x == 0:
        return 0, x

    # eat n-1 beager
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    # eat patty
    x -= 1
    ret += 1
    if x == 0:
        return ret, x

    # eat n-1 beager
    tmp, x = eat(n - 1, x)
    ret += tmp
    if x == 0:
        return ret, x

    # eat bread
    x -= 1 
        
    return ret, x


def main():
    tmp = input().split()
    n = int(tmp[0])
    x = int(tmp[1])
    global pnum
    global allnum
    pnum = [1]
    allnum = [1]
    for i  in range(1, 51):
        pnum.append(pnum[i-1] * 2 + 1)
        allnum.append(allnum[i-1] * 2 + 3)

    ans, tmp = eat(n, x)

    print(ans)

        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(3000)

N,X = (int(i) for i in input().split(' '))

L = [1]
P = [1]
for i in range(N):
    L.append(2*L[i] + 3) # 総枚数
    P.append(2*P[i] + 1) #　パティ数

# X はなんレベルバーガ内か？
#print(L)
#print(P)
# X はレベルlv バーガのどこにいるのか？
def find_level(lv, x):
    
#    print(lv, x)
    if lv == 0:
        return 1
    
    midlv = L[lv-1] + 2
    
    # 最上層
    if x == L[lv]:
#        print('最上層')
        return  P[lv]
    # 最上層から真ん中
    if x < L[lv] and x > midlv:
#        print('最上層〜真ん中')
        return find_level(lv-1,x - midlv) + 1 + P[lv-1]
    # ちょうど真ん中
    elif x == midlv:
#        print('真ん中')
        return 1 + P[lv-1] 
    # 真ん中〜最下層
    elif x < midlv and x > 1:
#        print('真ん中〜最下層')
        return find_level(lv-1, x - 1)
    # 最下層
    else:
#        print('最下層')
        return 0
        
    return(ret)

r = find_level(N, X)
print(r)

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
def b(n,x):
  if n==0 and x==1:
    return 1
  while n>0:
    z=(2**(n+2)-3)//2+1
    if x==1:
      return 0
    elif 1<x<z:
      return b(n-1,x-1)
    elif x==z:
      return 2**n
    elif z<x<(2**(n+2)-3):
      return 2**n + b(n-1,x-z)
    else:
      return 2**(n+1)-1
print(b(n,x))

Submission status: Accepted

Solution code:
burgerLens = [1 + 4 * (1 - 2**i)/(1-2) for i in range(0,51)]
numPatties = [1 + 2 * (1 - 2**i)/(1-2) for i in range(0,51)]

def recurse(n,k):
    if n == 0:
        return numPatties[0]
    if k <= n:
        return 0
    
    mid = burgerLens[n] // 2 + 1
    if k == mid:
        return 1 + numPatties[n-1]
    if k < mid:
        return recurse(n-1,k-1)
    if k > mid:
        return 1 + numPatties[n-1] + recurse(n-1,k-2-burgerLens[n-1])
    
N,K = map(int,input().split())
print(int(recurse(N,K)))

Submission status: Accepted

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

patty = []
patty.append(1)

lay = []
lay.append(1)

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


# print(patty)
# print(lay)

c = 0

for i in reversed(range(n+1)):
 #   print("i,x,c=", i, x, c)
    if x == lay[i]:
      #      print("i")
        c += patty[i]
        break

    elif x == lay[i-1]+2:  # ちょうど半分の時
       #     print("elif1")
        c += patty[i-1]+1
        break
    elif x < lay[i-1]+2:  # 半分より小さい時
        #    print("elif2")
        x = x-1
    else:  # 半分より大きい時
     #   print("el")
        x = x-2-lay[i-1]
        c += patty[i-1]+1

print(c)

Submission status: Accepted

Solution code:
def p_count(a, b):
    global l
    if b <= 0:
        return 0
    if a <= 0:
        return 1
    else:
        if b <= int(l[a][1]/2):
            return p_count(a-1, b-1)
        else:
            c = b - int(l[a][1]/2) - 1
            return l[a-1][0] + 1 + p_count(a-1, c)

l=list([[1,1]])
n,x = (int(i) for i in input().split())

for i in range(n):
    tmp = [(l[i][0]*2 + 1), (l[i][1]*2 + 3)]
    l.append(tmp)

print(p_count(n,x))

Submission status: Accepted

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


def all_pat_num(level):
    return(pow(2, level + 1) - 1)


def pat(level, x):
    if level == 0:
        if (x == 0):
            return 0
        else:
            return 1
    L = pow(2, level + 1) - 3
    if x == 1:
        ans = 0
    elif x <= 1 + L:
        ans = pat(level-1,x-1)
    elif x == 2 + L:
        ans = all_pat_num(level-1) + 1
    elif x < 2 + L + L:
        ans = all_pat_num(level-1) + 1 + pat(level - 1, x - 2 - L)
    else:
        ans = all_pat_num(level)
    return(ans)

print(pat(N, X))

Submission status: Accepted

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

lv_len=[1]
lv_pad=[1]

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

def solve(n,x):
  if n==0:
    return 1
  elif x==1:
    return 0
  else:
    if x <= lv_len[n]//2:
      return solve(n-1,x-1)
    elif x == lv_len[n]//2 +1:
      return 1 + solve(n-1,x-2)
    else:
      return lv_pad[n-1] + 1 + solve(n-1,x-(lv_len[n-1]+2))
    
print(solve(N,X))