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())
W=[0]*51
W[0]=1
for i in range(1,51):
  W[i]=W[i-1]*2 + 3
  
P=[0]*51
P[0]=1
for i in range(1,51):
  P[i]=P[i-1]*2+1
#nバーガーのX番目までのP  
def burger(n,x):
  if n==0:
    return 1
  #n-1バーガーの長さ
  l=W[n-1]
  if x==1:
    return 0
  if x==W[n]:
    return P[n]
  if x==1+l+1:
    return P[n-1]+1
  if 1<x<=l+1:
    return burger(n-1,x-1)
  if 1+l+1<x<=1+l+1+l:
    return P[n-1]+1+burger(n-1,x-(l+2))
  
print(burger(N, X))

Submission status: Accepted

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

l = [0 for _ in range(n+1)] #バーガーの長さ
p = [0 for _ in range(n+1)] #パティの枚数
l[0] = 1
p[0] = 1
for i in range(1,n+1):
    l[i] = 3 + 2 * l[i-1]
    p[i] = 1 + 2 * p[i-1]
#print(l)
#print(p)

def solv(n, x): #答えを返します
    #print(n, x)
    if n == 0:
        if x == 1:
            return 1
        if x == 0:
            return 0
    else:
        if x <= 1:
            return 0
        elif 1 < x <= l[n-1] + 1:
            return solv(n-1, x - 1)
        elif x == l[n-1] + 2:
            return solv(n-1, x - 2) + 1
        elif l[n-1] + 3 <= x:
            if x == l[n]:
                return p[n-1] + 1 + solv(n - 1, x - 3 - l[n - 1])
            else:
                return  p[n-1] + 1 + solv(n - 1, x - 2 - l[n - 1])

print(solv(n,x))

Submission status: Accepted

Solution code:
def bg(n,x):##nバーガーのx番目のパティの数
    if n==0:return 1
    l = wid[n-1]
    if x==1:return 0
    if 1<x<=l+1:
        return bg(n-1,x-1)
    if x==l+2:
        return pat[n-1]+1
    if l+2<x<=2*l+2:
        return pat[n-1]+1 + bg(n-1,x-l-2)
    if x==2*l+3 :
        return pat[n]

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

Submission status: Accepted

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

Submission status: Accepted

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

"""
　　レベルnの層数：a_0 = 1 , a_n = 2*a_(n-1)+3
レベルnのパティ数：b_0 = 1 , b_n = 2*b_(n-1)+1
"""

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

def patty(n):
    if n == 0:
        return 1
    else:
        return 2 * patty(n-1) + 1

def ans(n,x):
    if n == 0:
        return 1
    else:
        if x == 1:
            return 0
        if 1 < x <= thickness(n-1)+1:
            return ans(n-1,x-1)
        if x == thickness(n-1) + 2:
            return patty(n-1) + 1
        if thickness(n-1) + 2 < x <= 2 * thickness(n-1) + 2:
            return patty(n-1) + 1 + ans(n-1,x-2-thickness(n-1))
        if x == 2 * thickness(n-1) + 3:
            return 2 * patty(n-1) + 1

print(ans(N,X))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=1
b=1
sou=[a] #各バーガーの層の数
patty=[b] #各バーガーのパティの数
for i in range(49):
    a=(3+2*a)
    b=(1+2*b)
    sou.append(a)
    patty.append(b)
zan=x
total=0 #xまでに含まれるパティの数
ok=0
def check(num): #レベルiバーガーで調べる。
    global zan,total,ok
    if ok==1:
        return
    for i in range(5):
        if i==0 or i==4:
            zan-=1
        elif i==2:
            zan-=1
            total+=1
        else:
            zan-=sou[num-1]
            total+=patty[num-1]
        if zan==0:
            ok=1
            return
        elif zan<0:
            total-=patty[num-1]
            zan+=sou[num-1]
            #print(str(num-1)+" "+str(zan))
            check(num-1)
            if ok==1:
                break
check(n)
print(total)

Submission status: Accepted

Solution code:
def main():

    burgur = [0] * 51
    burgur[0] = 1
    pate = [0] * 51
    pate[0] = 1
    for i in range(50):
        burgur[i+1] = burgur[i] * 2 + 3
        pate[i+1] = pate[i] * 2 + 1
    
    N, X = map(int, input().split())

    X -= 1
    ans = 0
    for i in reversed(range(1, N+1)):
        if X == burgur[i] - 1:
            ans += pate[i]
            break
        elif X >= burgur[i-1] + 1:
            ans += pate[i-1] + 1
            X -= (burgur[i-1] + 2)
        else: 
            X -= 1
    if X == 0:
        ans += 1
    print(ans)
    

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

def MultiBurger(n,x):
    """
    レベルnバーガーの下からx枚に含まれるパティの量を計算する関数
    nBurger = 0 + n-1Burger + 1 + n-1Burger + 0
    0Burger = 1
    b=0
    p=1
    """
    sum=( 1<<n+2 )-3
    #sum: 総数
    middle=( 1<<n+1 )-1
    #middle: 真ん中のパティの番号
    num=(middle-1)//2
    #num: 1レベル小さいバーガーのパティの数

    if n==0 and x==1:
        return 1
    elif x==1:
        return 0

    elif x<middle-1:
        return MultiBurger(n-1,x-1)
    elif x==middle-1:
        return num
    elif x==middle:
        return num+1
    elif middle<x<sum-1:
        return num+1+MultiBurger(n-1,x-middle)
    else:
        return num*2+1
    
INPUT=input().split()
N=int(INPUT[0])
X=int(INPUT[1])
Paty=MultiBurger(N,X)

print(Paty)

Submission status: Accepted

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

B = [0] * 55
P = [0] * 55
P[0] = 1
for i in range(N):
    B[i + 1] = B[i] * 2 + 2
    P[i + 1] = P[i] * 2 + 1

def len(i):
    return B[i] + P[i]

def f(l, x):
    if l == 0:
        return 1
    if x == 1:
        return 0
    if x <= len(l - 1) + 1:
        return f(l - 1, x - 1)
    if x == len(l - 1) + 2:
        return P[l - 1] + 1
    if x <= len(l - 1) * 2 + 2:
        return P[l - 1] + f(l - 1, x - (len(l - 1) + 2)) + 1
    return P[l]

print(f(N, X))

Submission status: Accepted

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

a = [1]  # 厚さ
p = [1]  # パティの数
for i in range(N):
    a.append(2*a[-1] + 3)
    p.append(2*p[-1] + 1)


def f(n: int, x: int) -> int:
    """レベルnバーガーの下からx枚のパティの数
    """
    if x == 1:
        return 0 if n > 0 else 1
    elif x <= 1+a[n-1]:
        return f(n-1, x-1)
    elif x == 2 + a[n-1]:
        return p[n-1] + 1
    elif x <= 2*a[n-1] + 2:
        return p[n-1] + 1 + f(n-1, x - (2+a[n-1]))
    elif x == 2*a[n-1] + 3:
        return p[n]
    else:
        raise ValueError("xがレベルnバーガーの厚さより大きい, x={}, n={}".format(x, n))


if __name__ == "__main__":
    ans = f(N, X)
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
n,x=mii()
a,p=[1],[1]
for i in range(n):
    a.append(a[i]*2 +3)
    p.append(p[i]*2 +1)

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

Submission status: Accepted

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

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

    def dfs(n, x):
        a = A[n]
        b = B[n-1]
        if n == 0:
            return 1
        elif n >= x:
            return 0
        elif x == a//2:
            return b
        elif x == a//2 + 1:
            return b + 1
        elif x < a//2:
            return dfs(n-1, x-1)
        elif x > a//2 + 1:
            return dfs(n-1, x-(a//2)-1) + (b + 1)

    print(dfs(N, X))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    def dfs(n, x, ans):
        a = 1 + 4*(2**n - 1)
        if n == 0:
            return 1
        elif n >= x:
            return 0
        elif x == a//2:
            return 1 + 2*(2**(n-1) - 1)
        elif x == a//2 + 1:
            return 1 + 2*(2**(n-1) - 1) + 1
        elif x < a//2:
            ans += dfs(n-1, x-1, ans)
        elif x > a//2 + 1:
            ans += dfs(n-1, x-(a//2)-1, ans) + (1 + 2*(2**(n-1) - 1) + 1)
        return ans

    print(dfs(N, X, ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

L = [0]*(N+1)
L[0] = 1

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


def solve(n, x):
    #print(n, x)
    if x == L[n]:
        return(P[n])
    elif x <= n:
        return(0)
    else:
        ret = 0
        if x >= L[n-1] + 1:
            ret += P[n-1]
            x -= L[n-1] + 1
            if x > 0:
                ret += 1 + solve(n-1, x - 1)
        else:
            ret = solve(n-1, x-1)
        return(ret)


print(solve(N, X))

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**9)
N, X = map(int, input().split())

# A:厚さ P:パティの数
a = [1]
p = [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)


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

print(f(N, X))

Submission status: Accepted

Solution code:
def main():
    from functools import lru_cache
    import sys

    sys.setrecursionlimit(10 ** 7)

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

    size = [0] * (N + 1)
    patty = [0] * (N + 1)
    size[0] = 1
    patty[0] = 1
    for lv in range(1, N + 1):
        size[lv] = size[lv - 1] * 2 + 3
        patty[lv] = patty[lv - 1] * 2 + 1

    @lru_cache(maxsize=None)
    def burger(lv, x):
        if lv == 0:
            return int(x > 0)

        if x <= 1:
            return 0

        if x <= 1 + size[lv - 1]:
            return burger(lv - 1, x - 1)

        if x == 1 + size[lv - 1] + 1:
            return patty[lv - 1] + 1

        if x <= 1 + size[lv - 1] + 1 + size[lv - 1]:
            return patty[lv - 1] + 1 + burger(lv - 1, x - (1 + size[lv - 1] + 1))

        return patty[lv]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache

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

@lru_cache(maxsize=None)
def length(level):
    if level <= 0:
        return 1
    return length(level - 1) * 2 + 3

@lru_cache(maxsize=None)
def search(level, right):
    if level == 0:
        return 1

    ret = 0
    right -= 1
    if length(level - 1) <= right:
        ret += search(level - 1, length(level - 1))
        right -= length(level - 1)

        if right > 0:
            ret += 1
        right -= 1

    if 0 < right:
        ret += search(level - 1, right)
    return ret

print(search(N, X))

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
fi = x-1
aa = [1]
bb = [1]
a = 1
b = 1
for i in range(50):
    a = a*2 + 3
    b = b*2 + 1
    aa.append(a)
    bb.append(b)
    
def bu(lv , x):
    if lv == 0:
        return 1
    
    l = aa[lv-1]
    num = bb[lv-1]
    
    if x == 1:
        return 0
    elif x <= l+1:
        return bu(lv-1,x-1)
    elif x == l+2:
        return num +1
    elif x <= (l+1) * 2:
        return num + 1 + bu(lv-1,x-l-2)
    else:
        return num*2 + 1
    
print(bu(n,x))

Submission status: Accepted

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

a,p = [1], [1] #総枚数a,パティの枚数がp
for i in range(N): #a[i] = iバーガーの枚数
    a.append(a[i] *2 +3)
    p.append(p[i] *2 +1)

def f(N,X):
    if N == 0:
        if X>0:
            return 1
        else:
            return 0
        
    elif X <= 1 + a[N-1]:#真ん中以下の場合
        return f(N-1,X-1)#N-1バーガーでX-1（バンズがふえているので）枚食べるのと同じ
    else:
        return p[N-1] +1 + f(N-1, X-2-a[N-1])#N-1バーガー+真ん中パティ+N-1バーガーのうち[X-2-N-1バーガーの枚数]分だけ食べる
print(f(N,X))

Submission status: Accepted

Solution code:
from itertools import permutations
import sys

sys.setrecursionlimit(10 ** 6)
from bisect import *
from collections import *
from heapq import *

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def SI(): return sys.stdin.readline()[:-1]
def LLI(rows_number): return [LI() for _ in range(rows_number)]
int1 = lambda x: int(x) - 1
def MI1(): return map(int1, sys.stdin.readline().split())
def LI1(): return list(map(int1, sys.stdin.readline().split()))
p2D = lambda x: print(*x, sep="\n")
dij = [(1, 0), (0, 1), (-1, 0), (0, -1)]

def main():
    memo={}
    def f(lv,x):
        if lv==0:return 1
        if x==1:return 0
        if x==ss[lv]:return pp[lv]
        if (lv,x) in memo:return memo[lv,x]
        if x<=ss[lv-1]+1:res=f(lv-1,x-1)
        elif x==ss[lv-1]+2:res=pp[lv-1]+1
        else:res=pp[lv-1]+f(lv-1,x-ss[lv-1]-2)+1
        memo[lv,x]=res
        return res

    ss=[1]
    pp=[1]
    for i in range(50):
        ss.append(ss[-1]*2+3)
        pp.append(pp[-1]*2+1)
    #print(ss)
    #print(pp)
    n,x=MI()
    print(f(n,x))



main()

Submission status: Accepted

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

# a : レベルlでの長さ
# p : レベルlでのP数
a,p = [1], [1]
for i in range(n):
    a.append(2*a[-1]+3)
    p.append(2*p[-1]+1)

# f(l,x) : レベルlでの下からxまでのP数
def f(l, x):
    if l==0:
        if x>0:
            return 1
        else:
            return 0
    
    elif x<=a[l-1]+1:
        return f(l-1, x-1)

    else:
        return p[l-1] + 1 + f(l-1, x-a[l-1]-2)

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 make_burger(i, x):
    if i == 0:
        return 1 if x > 0 else 0
    mid = (b[i] + 1) // 2
    if mid > x:
        return make_burger(i - 1, x - 1)
    elif mid == x:
        return p[i - 1] + 1
    else:
        return p[i - 1] + 1 + make_burger(i - 1, x - mid)
    

n, x = map(int, input().split())
p = [1]
b = [1]

for _ in range(n):
    p.append(p[-1] * 2 + 1)
    b.append(b[-1] * 2 + 3)

print(make_burger(n, x))

Submission status: Accepted

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

    def dfs(n, x, ans):
        a = 1 + 4*(2**(n-1) - 1)
        if n == 1:
            return 1
        elif (n-1) >= x:
            return 0
        elif x == a//2:
            return 1 + 2*(2**(n-2) - 1)
        elif x == a//2 + 1:
            return 1 + 2*(2**(n-2) - 1) + 1
        elif x < a//2:
            ans += dfs(n-1, x-1, ans)
        elif x > a//2 + 1:
            ans += dfs(n-1, x-(a//2)-1, ans) + (1 + 2*(2**(n-2) - 1) + 1)
        return ans

    print(dfs(N+1, X, ans))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

def f(n,x):
  if n==0:
    if x>0:return 1
    else:return 0
  if x<=(2**(n+2)-3-1)//2:
    return f(n-1,x-1)
  else:
    tmp=x-((2**(n+2)-3-1)//2+1)
    return 2**n-1+1+f(n-1,tmp)
  
print(f(n,x))

Submission status: Accepted

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

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

print(f(n,x))

Submission status: Accepted

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

def f(n,x):
  if n==0:
    if x>0:return 1
    else:return 0
  if x<=(2**(n+2)-3-1)//2:
    return f(n-1,x-1)
  else:
    tmp=x-((2**(n+2)-3-1)//2+1)
    return 2**n-1+1+f(n-1,tmp)
  
print(f(n,x))

Submission status: Accepted

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


def f(fn,fx):
    if fn == 0 and fx == 1:
        return 1
    elif fx == 1:
        return 0
    elif fx == q[fn]:
        return p[fn]
    elif fx == q[fn]//2+1:
        return 1+p[fn-1]
    elif 1 < fx < q[fn]//2+1:
        return f(fn-1, fx-1)
    else:
        return p[fn-1] + 1 + f(fn-1, fx-(q[fn-1]+2))


print(f(n,x))

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

def func(level, x):
    debug(level, x)
    if level == 0 and x == 1:
        return 1
    elif level == 0 and x <= 0:
        return 0
    npast = num[level - 1]
    if x <= npast + 1:
        tmp = func(level - 1, x - 1)
        debug('a', level, x, tmp)
        return tmp
    elif x == npast + 2:
        tmp = func(level - 1, x - 2)
        debug('b', level, x, tmp + 1)
        return tmp + 1
    else:
        tmp1  = num2[level - 1]
        debug('tmp1', tmp1)
        if x == npast * 2 + 3:
            debug('aa', x - npast - 3)
            tmp2 = func(level - 1, x - npast - 3)
        else:
            tmp2 = func(level - 1, x - npast - 2)
        debug('c', level, x, tmp1 + 1 + tmp2)
        return tmp1 + 1 + tmp2

n, x = MAP()
num = [1]
for i in range(2, n + 1):
    num.append(2 * num[-1] + 3)
num2 = [1]
for i in range(2, n + 1):
    num2.append(2 * num2[-1] + 1)
debug(num)
debug(num2)
ans = func(n, x)
print(ans)

Submission status: Accepted

Solution code:
def dfs(l,x):
    if x == 0:
        return 0
    if l == 0:
        return 1
    if x == 1:
        return 0
    if x <= num[l] // 2:
        return dfs(l-1,x-1)
    if x == num[l]:
        x -= 1
    return patty[l-1] + 1 + dfs(l-1,x-num[l]//2-1)
n,x = map(int,input().split())
patty = [1]
num = [1]
for i in range(1,51):
    patty.append(patty[i-1]*2+1)
    num.append(num[i-1]*2+3)
print(dfs(n,x))

Submission status: Accepted

Solution code:
def burger_size(N):
    if N == 0:
        return 1
    return 3 + 2 * burger_size(N - 1)

def burger_patty_num(N):
    if N == 0:
        return 1
    return 1+ 2 * burger_patty_num(N - 1)

def patty_num(N, X):
    if X == 0:
        return 0
    if N == 0:
        return 1
    if X <= 1 + burger_size(N - 1):
        return patty_num(N - 1, X - 1)
    elif X == 2 + burger_size(N - 1):
        return 1 + burger_patty_num(N - 1)
    elif X <= 2 + 2 * burger_size(N - 1):
        return 1 + burger_patty_num(N - 1) + patty_num(N - 1, X - (2 + burger_size(N - 1)))
    else:
        return 1 + 2 * burger_patty_num(N - 1)
        
    
N, X = map(int, input().split())
print(patty_num(N, X))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.buffer.readline().split()]
def I(): return int(sys.stdin.buffer.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,x = LI()
    l = [4*2**i-3 for i in range(n+1)]
    s = [2*2**i-1 for i in range(n+1)]
    ans = 0
    while x:
        if x == l[n]:
            ans += s[n]
            break
        if x <= l[n-1]+1:
            n -= 1
            x -= 1
        elif x < l[n]:
            ans += 1+s[n-1]
            x -= 2+l[n-1]
            n -= 1
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def layers(n):
    result = 1
    for _ in range(0, n):
        result = result * 2 + 3
    return result


def meat(n):
    result = 1
    for _ in range(0, n):
        result = result * 2 + 1
    return result


def calc(n, x):
    before_layer = layers(n - 1)
    before_meat = meat(n - 1)
    if x == 1:
        return 1 if n == 0 else 0
    elif x <= 1 + before_layer:
        return calc(n - 1, x - 1)
    elif x == 2 + before_layer:
        return 1 + before_meat
    elif x <= 2 + 2 * before_layer:
        return 1 + before_meat + calc(n - 1, x - 2 - before_layer)
    elif x == 3 + 2 * before_layer:
        return 2 * before_meat + 1


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

def f(N, X):
    if N == 0 and X > 0:
        return 1
    elif N == 0 and X <= 0:
        return 0
    elif X <= l[N-1] + 1:
        return f(N-1, X-1)
    else: # X > l[N-1] + 2:
        return p[N-1] + f(N-1, X - 2 - l[N-1]) + 1
    #elif X == l[N-1] + 2:
    #    return p[N-1] + 1

print(f(N, X))

Submission status: Accepted

Solution code:
import numpy as np
import collections
N, X = list(map(int,input().split()))

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

def f(N, X):
    if N == 0 and X > 0:
        return 1
    elif N == 0 and X <= 0:
        return 0
    elif X <= l[N-1] + 1:
        return f(N-1, X-1)
    else: # X > l[N-1] + 2:
        return p[N-1] + f(N-1, X - 2 - l[N-1]) + 1
    #elif X == l[N-1] + 2:
    #    return p[N-1] + 1

print(f(N, X))

Submission status: Accepted

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

def solve(n,x,ans):
    if x == 0:
        return ans
    if n == 0:
        return ans + 1
    mid = layer_n[n]//2 + 1
    if x < mid:
        return solve(n-1,x-1,ans)
    elif x == mid:
        return ans + P_n[n-1]+1
    else:
        x -= 2 + layer_n[n-1]
        ans += P_n[n-1]+1
        return solve(n-1,x,ans)

print(solve(N,X,0))

Submission status: Accepted

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

all, pate = [1], [1]
for i in range(N):
  all.append(all[i]*2 + 3)
  pate.append(pate[i]*2 + 1)

def f(N, X):
  if N == 0:
    return 1
  elif X == 1:
    return 0
  elif X <= 1 + all[N-1]:
    return f(N-1, X-1)
  elif X == 2 + all[N-1]:
    return 1 + pate[N-1]
  elif X < 3 + 2 * all[N-1]:
    return 1 + pate[N-1] + f(N-1, X-2-all[N-1])
  elif X == 3 + 2 * all[N-1]:
    return 2 * pate[N-1] + 1
print(f(N, X))

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,x = map(int, input().split())
    #b[i]:レベルiバーガーの層数(max:n)
    b = [1]
    for i in range(n):
        b.append(b[i]*2+3)

    #p[i]:レベルiバーガーのパティの数
    p = [1]
    for i in range(n):
        p.append(p[i]*2+1)

    #n:レベル　x:層数
    def solve(n, x):
        if n==0:
            if x==0:
                return 0
            else:
                return 1
        res = 0
        if b[n]//2 == x:
            res += p[n-1]
        elif b[n] == x:
            res += p[n-1]*2 + 1
        elif x == 0:
            res = 0
        elif b[n]//2 < x:
            res += p[n-1] + 1 + solve(n-1, x-b[n]//2-1)
        else:
            res += solve(n-1, x-1)
        return res

    print(solve(n, x))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import fractions
from collections import deque
from collections import defaultdict
sys.setrecursionlimit(10**7)

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

g = [1] * 51
p = [1] * 51

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


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

    if x <= g[n - 1] + 1:
        return rec(n - 1, x - 1)
    elif x == g[n - 1] + 2:
        return p[n - 1] + 1
    elif x <= 2 * g[n - 1] + 2:
        return rec(n - 1, x - g[n - 1] - 2) + p[n - 1] + 1
    else:
        return p[n]


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

Submission status: Accepted

Solution code:
N,X=map(int,input().split(' '))
l = 1
p = 1
L=[]
P=[]
for i in range(N):
    l = 2*l+3
    p = 2*p+1
    L.append(l)
    P.append(p)
def pans(l,x):
    if l==1:
        return list('BPPPB'[:x]).count('P')
    elif x<=L[l-2]+1:
        return pans(l-1,x-1)
    else:
        return P[l-2]+1+pans(l-1,x-(2+L[l-2]))
print(pans(N,X))

Submission status: Accepted

Solution code:

import numpy as np
from functools import *
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline




def acinput():
    return list(map(int, input().split(" ")))


def II():
    return int(input())

directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,X=acinput()

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

def f(N,k):
    
        
    if N == 0 and k>=1:
        return 1
    
    if k <= 1:
        return 0
    
    if k<=n[N-1]+1:
        return f(N-1,k-1)
    else:
        r=k-n[N-1]-2
        return p[N-1]+f(N-1,r)+1


print(f(N,X))

Submission status: Accepted

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

def make_burger(i, x):
    if i == 0:
        return 1 if x >= 1 else 0
    center_num = (a[i] + 1) // 2
    if center_num > x:
        return make_burger(i - 1, x - 1)
    elif center_num == x:
        return p[i - 1] + 1
    else:
        return p[i - 1] + 1 + make_burger(i - 1, x - center_num)


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

print(make_burger(n, x))

Submission status: Accepted

Solution code:
def dfs(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    elif x <= 1 + a[n - 1]:
        return dfs(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + dfs(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(dfs(n, x))

Submission status: Accepted

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

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

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + ans[N-1]:
        return f(N-1, X-1)
    elif X == 2 + ans[N-1]:
        return pat[N-1] + 1
    elif X <= 2 + 2*ans[N-1]:
        return pat[N-1] + 1 + f(N-1, X-2-ans[N-1])
    else:
        return 2*pat[N-1] + 1

print(f(n, x))

Submission status: Accepted

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

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

def calc(x, nn):
    if x == 1:
        return 1 if nn == 0 else 0
    tt = bag_list[nn-1] + 2
    # print(nn,x,tt)
    if x == tt:
        # print(plist[nn-1] + 1)
        return plist[nn-1] + 1
    elif x == bag_list[nn]:
        # print(plist[nn])
        return plist[nn]
    elif x < tt:
        # print(0)
        return calc(x-1, nn-1)
    elif x > tt:
        # print(plist[nn-1] + 1)
        return calc(x-1-1-bag_list[nn-1], nn-1) + plist[nn-1] + 1

print(calc(x, n))