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:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
N,X = map(int,input().split())
memo = {}
memo[(1,1)] = 1
def cost(N,X):
 L=2**(N+1)-3
 ans=0
 if X==1:
  ans=0
 elif X==2**(N+1)-3:
  ans=2**N-1
 elif X==(L+1)//2:
  if (N-1,X-2) in memo:
   ans=memo[(N-1,X-2)]+1
  else:
   ans=cost(N-1,X-2)+1
 elif X>(L+1)//2:
  if (N-1,X-((L+1)//2)) in memo:
   ans=2**(N-1)+memo[(N-1,X-((L+1)//2))]
  else:
   ans=2**(N-1)+cost(N-1,X-((L+1)//2))
 else:
  if (N-1,X-1) in memo:
   ans=memo[(N-1,X-1)]
  else:
   ans=cost(N-1,X-1)
 memo[(N,X)]=ans
 return ans
print(cost(N+1,X))

Submission status: Accepted

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

Submission status: Accepted

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

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


p=0
while x!=0:
    if n==0:
        p+=1
        x=0
    elif x<=h[n-1]+1:
        x=x-1
    elif x==h[n-1]+2:
        p+=1
        x=x-2
    elif x<=2*h[n-1]+2:
        p+=bp[n-1][1]+1
        x=x-h[n-1]-2
    else:
        p+=2*bp[n-1][1]+1
        x=0
    n=n-1

print(p)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

T = [0] * (N + 1) # レベルiバーガーの厚さ
P = [0] * (N + 1) # レベルiバーガーのパティの数

T[0] = 1
P[0] = 1

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

# Nバーガー,X枚目
stack = [[N,X]]
ans = 0

while stack:
  n, x = stack.pop()
  if x <= 0:
    continue
  if x >= T[n]:
    ans += P[n]
    continue
  if n == 0:
    ans += P[n]
    continue
  stack.append([n - 1,x - 1])
  ans += (x >= T[n - 1] + 2) * 1
  stack.append([n - 1, x - (T[n - 1] + 2)])

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

T = [0] * (N + 1) # レベルiバーガーの厚さ
P = [0] * (N + 1) # レベルiバーガーのパティの数

T[1] = 5
P[1] = 3

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

# Nバーガー,X枚目
stack = [[N,X]]
ans = 0

while stack:
  n, x = stack.pop()
  if x <= 0:
    continue
  if x >= T[n]:
    ans += P[n]
    continue
  if n == 1:
    ans += min(x - 1,3)
    continue
  stack.append([n - 1,x - 1])
  ans += (x >= T[n - 1] + 2) * 1
  stack.append([n - 1, x - (T[n - 1] + 2)])

print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

T = [0] * (N + 1) # レベルiバーガーの厚さ
P = [0] * (N + 1) # レベルiバーガーのパティの数

T[1] = 5
P[1] = 3

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

# Nバーガー,X枚目
stack = [[N,X]]
ans = 0

while stack:
  n, x = stack.pop()
  if n == 1:
    ans += min(x - 1,3)
    continue
  if x <= 1: # 1枚目の場合はパティなし
    continue
  if x < 1 + T[n - 1]: # 一つ目のレベルn - 1バーガーに収まる場合
    stack.append([n - 1, x - 1])
  elif x <= 1 + T[n - 1]:
    ans += P[n - 1]
  elif x == 2 + T[n - 1]:
    ans += P[n - 1]
    ans += 1
  elif x < 2 + T[n - 1] * 2:
    ans += P[n - 1]
    ans += 1
    stack.append([n - 1, x - (T[n - 1] + 2)])
  else:
    ans += P[n - 1] * 2
    ans += 1

print(ans)

Submission status: Accepted

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

    # p_n = 1 + 2 * p_n-1
    # l_n = 3 + 2 * p_n-1
    # p0 = 1
    # l0 = 1
    pl = [(0, 0)] * (n + 1)
    pl[0] = (1, 1)

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

    res = 0

    while n and x > 0:
        x -= 1  # bands
        p, l = pl[n - 1]
        if x == l * 2 + 2 or x == l * 2 + 1:
            res += 2 * p + 1
            break

        if x == l or x == l + 1:
            res += p + (x - l)
            break

        if x < l:
            n -= 1
        else:
            res += p + 1
            x -= l

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    # p_n = 1 + 2 * p_n-1
    # l_n = 3 + 2 * p_n-1
    # p0 = 1
    # l0 = 1
    p = [0] * (n + 1)
    l = [0] * (n + 1)
    p[0] = 1
    l[0] = 1
    for i in range(1, n + 1):
        p[i] = 1 + 2 * p[i - 1]
        l[i] = 3 + 2 * l[i - 1]

    res = 0
    while n and x > 0:
        x -= 1  # bands

        if x == l[n - 1] or x == l[n - 1] + 1:
            res += p[n - 1] + (x - l[n - 1])
            break
        if x == l[n - 1] * 2 + 2:
            res += 2 * p[n - 1] + 1
            break
        if x < l[n - 1]:
            n -= 1
        else:
            res += p[n - 1] + 1
            x -= l[n - 1]

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
# from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,x = MI()

def mycalc(n,x):
    M = 4*(2**n) - 3
    m = (M//2) + 1
    if n==0:
        return 1
    if x==1:
        return 0
    elif x>=2 and x<m:
        return mycalc(n-1,x-1)
    elif x==m:
        return mycalc(n-1,x-2) + 1
    elif x>m and x<M:
        return mycalc(n-1,x-m) + ( 2**(n+1) - 2 )//2 + 1
    elif x==M:
        return 2**(n+1) - 1
    else:
        print("E")
ans = mycalc(n,x)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint
from statistics import mean,median,mode

INF = float("inf")

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

def I():
    return int(input())

def MI():
    return map(int,input().split())

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

def CI(n):
    return [ int(input()) for _ in range(n) ]

def LI(n):
    return [ list(map(int,input().split())) for _ in range(n) ]

def S():
    return input()

def MS():
    return input().split()

def RS():
    return list(input().split())

def CS(n):
    return [ input() for _ in range(n) ]

def LS(n):
    return [ list(input().split()) for _ in range(n) ]

n,x = MI()

def mycalc(n,x):
    M = 4*(2**n) - 3
    m = (M//2) + 1
    if n==0:
        return 1
    if x==1:
        return 0
    elif x>=2 and x<m:
        return mycalc(n-1,x-1)
    elif x==m:
        return mycalc(n-1,x-2) + 1
    elif x>m and x<M:
        return mycalc(n-1,x-m) + ( 2**(n+1) - 2 )//2 + 1
    elif x==M:
        return 2**(n+1) - 1
    else:
        print("E")
ans = mycalc(n,x)
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

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

# レベルNバーガーの厚さ = (レベルN - 1バーガーの厚さ) * 2 + 3
# レベル1〜Nの厚さを先に求めておく

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

# レベルNバーガーをX枚目まで食べたとき、パティを何枚食べるか
# レベルN - 1バーガーの厚さをtとする
# X = 1 : 0枚
# X <= t + 1 : レベルN - 1バーガーのX - 1枚目まで
# X = t + 2 : レベルN - 1バーガーのt枚目まで + 1
# X < t * 2 + 3 : レベルN - 1バーガーのすべてと、1枚と、レベルN - 1バーガーのX - (t + 2)枚目まで
# X = t : レベルN - 1バーガーのすべて * 2 + 1

def bargar(n,x):
  if n == 1:
    return min(x - 1, 3)
  t = T[n - 1] # レベルNバーガーの厚さ
  if x == 1:
    return 0
  elif x <= t + 1:
    return bargar(n - 1, x - 1)
  elif x == t + 2:
    return bargar(n - 1, t) + 1
  elif x < t * 2 + 3:
    return bargar(n - 1,t) + 1 + bargar(n - 1, x - (t + 2))
  else:
    return bargar(n - 1,t) * 2 + 1

print(bargar(N,X))

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, x = list(map(int, readline().split()))
    l = [0] * (n + 1)
    b = [0] * (n + 1)

    l[0] = 1
    b[0] = 1

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

    ans = 0
    rem = x
    level = n

    while rem and level > 0:
        if rem >= l[level - 1] + 2:
            ans += b[level - 1] + 1
            rem -= (l[level - 1] + 2)
            level -= 1
        elif rem == l[level - 1] + 1:
            rem -= (l[level - 1] + 1)
            ans += b[level - 1]
        else:
            rem -= 1
            level -= 1

    if level == 0 and rem:
        ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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


print(f(N=n, X=x))

Submission status: Accepted

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

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

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

def solve(n,x):
    if n == 0:
        if x == 1:
            return 1
        return 0
    if x == a[n]:
        return b[n]
    if x >= a[n]//2+1:
        return b[n-1] + 1 + solve(n-1,x-a[n]//2-1)
    if x >= 1:
        return solve(n-1,x-1)
    return 0

print(solve(N,X))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,X = IL()

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

def count_beef(N,X):
  burger = width[N]
  ans = 0
  if X == 1:
    if N == 0:
      return 1
    else:
      return 0
  elif 2<=X<=1+width[N-1]:
    return count_beef(N-1,X-1)
  elif X == 2+width[N-1]:
    return beef[N-1]+1
  elif 3+width[N-1]<=X<=2+width[N-1]*2:
    return beef[N-1] + 1 + count_beef(N-1,X-2-width[N-1])
  else:
    return beef[N]
  
print(count_beef(N,X))

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
from collections import defaultdict
from collections import deque
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)


#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####GCD#####
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,X = IL()

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

def count_beef(N,X):
  burger = width[N]
  ans = 0
  if X == 1:
    if N == 0:
      return 1
    else:
      return 0
  elif 2<=X<=1+width[N-1]:
    return count_beef(N-1,X-1)
  elif X == 2+width[N-1]:
    return count_beef(N-1,X-2)+1
  elif 3+width[N-1]<=X<=2+width[N-1]*2:
    return beef[N-1] + 1 + count_beef(N-1,X-2-width[N-1])
  else:
    return beef[N]
  
print(count_beef(N,X))

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def solve(i, x):  # レベルiバーガーの下からxこ
	if i == 0:
		if x <= 0:
			return 0
		else:
			return 1
	if x <= L[i-1]+1:
		ret = solve(i-1, x-1)
	else:
		ret = P[i-1]+1+solve(i-1, x-L[i-1]-2)
	return ret

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

print(solve(N, X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
n, x = [int(x) for x in input().split()]

total = [1]
p = [1]

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

ans = 0

# print(total)

def solve(x, i):
    global ans
    if x == 0:
        ans += 1
        return
    if i <= 1 + total[x - 1]:
        if i - 1 > 0:
            solve(x - 1, i - 1)
    else:
        ans += 1 + p[x - 1]
        if i - (2 + total[x - 1]) > 0:
            solve(x - 1, i - (2 + total[x - 1]))

solve(n, x)
print(ans)

Submission status: Accepted

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

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

def func(x, n):
    if n == 0:
        return 1
    if x <= 1:
        return 0
    elif 2 <= x <= 2**(n+1)-2:
        return func(x-1, n-1)
    elif x == 2**(n+1)-1:
        return 2**n-1+1
    elif 2**(n+1) <= x:
        return 2**n-1+1+func(x-(2**(n+1)-1), n-1)

print(func(x, n))

Submission status: Accepted

Solution code:
from functools import lru_cache

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

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

@lru_cache(maxsize=None)
def calc(level, N):
    if level == 0:
        return 1 if N > 0 else 0

    N = min(N, size(level))

    ret = 0
    N -= 1

    if N >= size(level - 1):
        ret += calc(level - 1, size(level - 1))
        N -= size(level - 1)

        if N >= 1:
            ret += 1
            N -= 1

    return ret + calc(level - 1, N)

print(calc(N, X))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

Submission status: Accepted

Solution code:
level, num_eat = map(int,input().split())

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

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

def f(level, x):
    if level == 0:
        return 1
    elif x == 1:
        return 0
    elif 1 < x <= 1 + get_layers(level-1):
        return f(level-1, x-1)
    elif x == 2 + get_layers(level-1):
        return get_patty(level - 1) + 1
    elif 2 + get_layers(level-1) < x <= 2 + 2 * get_layers(level-1):
        return get_patty(level-1) + 1 + f(level-1,x-2-get_layers(level-1))
    elif x == 3 + 2*get_layers(level-1):
        return 2*get_patty(level - 1) + 1

print(f(level, num_eat))

Submission status: Accepted

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

def solve(n,x):
    total=[1]
    paty=[1]
    for i in range(50):
        total.append(total[i]*2+3)
        paty.append(paty[i]*2+1)

    @lru_cache(maxsize=None)
    def f(N,X):
        if N==0 and X<=0:
            return 0
        elif N==0 and X>0:
            return 1
        elif X<=total[N-1]+1:
            return f(N-1, X-1)
        else:
            return paty[N-1]+1+f(N-1, X-total[N-1]-2)
    return print(f(n,x))

if __name__=='__main__':
    n,x=map(int,input().split())
    solve(n,x)

Submission status: Accepted

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

total=[1]
paty=[1]
for i in range(n):
    total.append(total[i]*2+3)
    paty.append(paty[i]*2+1)

def rec(N, X): 
    if N==0 and X<=0:
        return 0 
    elif N==0 and X>0:
        return 1
    elif X<=1+total[N-1]:
        return rec(N-1, X-1)
    else:
        return paty[N-1] + 1 + rec(N-1, X-2-total[N-1])

print(rec(n, x))

Submission status: Accepted

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

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

print(f(n,x))

Submission status: Accepted

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

def count_p(n, x):
  if x == 0:
    return 0
  elif n == 0:
    return 1
  elif x > 2**(n+1)-2:
    return 2**(n)-1 + 1 + count_p(n-1, min(x-(2**(n+1)-1), 2**(n+1)-3))
  else:
    return count_p(n-1, x-1)
  
print(count_p(n,x))

Submission status: Accepted

Solution code:
N, X = 2, 7

N, X = 50, 4321098765432109

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


def calculate(n, x):
    p = 1
    level = 0
    dialations = [1]

    for i in range(n):
        p = 2 * p + 3
        level = level + 1
        dialations.append(p)

    # print(dialations)
    # print(level)

    res = calculate2(level, dialations, x - 1)
    print(res)


def calculate2(currentLevel, dialations, x):
    keyPoint0 = 0
    keyPoint1 = keyPoint0 + dialations[currentLevel - 1] + 1

    if currentLevel == 0:
        return 1

    if x == -1:
        return 2 * calculate2(currentLevel - 1, dialations, -1) + 1

    if x == keyPoint0:
        return 0

    if (x > keyPoint0) and (x < keyPoint1):
        return calculate2(currentLevel - 1, dialations, x - 1)

    if x == keyPoint1:
        return calculate2(currentLevel - 1, dialations, -1) + 1

    if (x > keyPoint1):
        return calculate2(currentLevel - 1, dialations, -1) + 1 + calculate2(currentLevel - 1, dialations,
                                                                             x - dialations[currentLevel - 1] - 2)


calculate(N, X)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
def solve(n, i):
    if n==0:
        return 1
    if i==0:
        return 0
    if i<(2**(n+2)-3)//2:
        return solve(n-1, i-1)
    if i==(2**(n+2)-3)//2:
        return 2**n
    if i<2**(n+2)-4:
        return 2**n + solve(n-1, i-(2**(n+2)-3)//2-1)
    return 2**(n+1) - 1
print(solve(n, x-1))

Submission status: Accepted

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

arr=[1]*(n+1)
patty=[1]*(n+1)
for i in range(n):
    arr[i+1]=3+2*arr[i]
    patty[i+1]=1+2*patty[i]

def f(n,x):
    
    if n==0:
        return 1
    elif x==1:
        return 0
    elif x==arr[n] or x==arr[n]-1:
        return patty[n]
    elif x<arr[n]//2+1:
        return f(n-1,x-1)
    elif x==arr[n]//2+1:
        return patty[n-1]+1
    else:
        return patty[n]-f(n-1,arr[n]-x-1)

print(f(n,x))

Submission status: Accepted

Solution code:
# Python3 (3.4.3)
import sys
input = sys.stdin.readline

# -------------------------------------------------------------
# function
# -------------------------------------------------------------
def dfs(N,X):
    # Lv.0
    if N == 0:
        # 調べる数が残っていれば : 1
        if X > 0:
            return 1
        # 残ってなければ : 0
        else:
            return 0
    # Lv.1以上
    else:
        # 下側の Lv.n-1 までの場合
        if X <= 1 + T[N-1]:
            return dfs(N-1,X-1)
        # 真ん中のパティまでの場合
        elif X == 1 + T[N-1] + 1:
            return P[N-1] + 1
        # 上側の Lv.n-1 までの場合
        else:
            return P[N-1] + 1 + dfs(N-1,X-2-T[N-1])

# -------------------------------------------------------------
# main
# -------------------------------------------------------------
N,X = map(int,input().split())

# 事前計算
# T[i] : Lv i バーガーの層数
# P[i] : Lv i バーガーのパティ数
T,P = [0]*(N+1),[0]*(N+1)
T[0],P[0] = 1,1
for i in range(N):
    T[i+1] = T[i]*2 + 3
    P[i+1] = P[i]*2 + 1

print(dfs(N,X))