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:
pa = [1]
atu = [1]

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

Submission status: Accepted

Solution code:
import sys

# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
import heapq
import decimal
# import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, x = ns()
    lim = 51
    total = [int(0) for _ in range(lim)]
    P_total = [int(0) for _ in range(lim)]

    total[0] = 1
    for i in range(1, lim):
        total[i] = total[i - 1] * 2 + 3

    P_total[0] = 1
    for i in range(1, lim):
        P_total[i] = P_total[i - 1] * 2 + 1

    ans = 0
    base = 1
    L = n
    flg = True
    while base != x and L != 0:
        if base + total[L] // 2 <= x and flg:
            base += total[L] // 2
            ans += P_total[L - 1] + 1
            flg = False
        else:
            flg = True
            base += 1
            L -= 1
            if L == 0:
                ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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


print(fx(N, X))

Submission status: Accepted

Solution code:
def calc(n,x):
  if x==1:
    if n==0:
      ans=1
    else:
      ans=0
  elif 1 < x < (num[n]+1)//2:
    ans= calc(n-1,x-1)
  elif x== (num[n]+1)//2:
    ans= pat[n-1]+1
  elif (num[n]+1)//2 < x <num[n]:
    ans= pat[n-1]+1+ calc(n-1, x- (num[n]+1)//2)
  else:   # x=num[n]
    ans= pat[n]
  return ans


N,X=map(int,input().split())
num= [1]
pat= [1]
for i in range(1,N+1):
  num.append(num[-1]*2+3)
  pat.append(pat[-1]*2+1)

print(calc(N,X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def fn(k):
    return pow(2, k + 2) - 3

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

    sum_f = fn(n - 1)
    if x <= sum_f + 1:
        rec += pn(n - 1, x - 1)

    elif x == sum_f + 2:
        rec += pow(2, n)

    else:
        rec += pow(2, n) + pn(n - 1, x - (sum_f + 2))

    return rec

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

Submission status: Accepted

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


def saiki(n, x):
    #print(n, x)
    if n == 5:
        if x == 1:
            return 0
        elif x <= 4:
            return x-1
        else:
            return 3

    if x <= 1:
        return 0
    elif x <= 1 + (n-3)//2:
        return saiki((n-3)//2, x-1)
    elif x == 1 + (n-3)//2 + 1:
        return saiki(x - 2, x - 2) + 1
    elif x <= 1 + (n-3)//2 + 1 + (n-3)//2:
        return saiki((n - 3) // 2, (n - 3) // 2) + 1 + saiki((n - 3) // 2, x - ((n-3)//2+2))
    else:
        return 2 * saiki((n - 3) // 2, (n - 3) // 2) + 1


maisu = 1
for i in range(N):
    maisu = 2 * maisu + 3

ans = saiki(maisu, X)

print(ans)

Submission status: Accepted

Solution code:
N,X=list(map(int,input().split()))
p=[]
a=[]
def search(N):
    if N==0:
        p.append(1)
        a.append(1)
        return 1,1
    else:
        search(N-1)
        p.append(2*p[N-1]+1)
        a.append(2*a[N-1]+3)
search(N)
def bug(N,X):#p,a
    if N==0 and X>=1:return 1
    if X==1:return 0
    if 1<X<=1+a[N-1]:
        return bug(N-1,X-1)
    elif X==a[N-1]+2:
        return p[N-1]+1
    elif a[N-1]+2<X<=2+2*a[N-1]:
        return p[N-1]+1+bug(N-1,X-2-a[N-1])
    elif X==3+2*a[N-1]:
        return 2*p[N-1]+1
print(bug(N,X))

Submission status: Accepted

Solution code:
N,X = (int(x) for x in input().split())
P = [1]
for i in range(N):
    P.append(1+2*(P[-1]))
PB = [1]
for i in range(N):
    PB.append(3+2*(PB[-1]))
ans = 0
for i in range(N+1):
    if X == PB[N-i]:
        if N - i > 0:
            ans += 1 + (2*P[N-1-i])
            break
        else:
            ans += 1
            break
    elif X == 2 + PB[N-1-i]:
        ans += 1 + P[N-1-i]
        break
    elif X == 1:
        break
    elif X < 2 + PB[N-1-i]:
        X -= 1
    else:
        X -= 2 + PB[N-1-i]
        ans += 1 + P[N-1-i]
print(ans)

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

ans = rec(n, x, a, p)
print(ans)

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
Size = [1]
Patty = [1]

for i in range(51):
    Size.append(Size[-1] * 2 + 3)
    Patty.append(Patty[-1] * 2 + 1)


def count_p(n, x):
    if x == 0:
        return 0
    if n == 0:
        return min(x, 1)
    if (Size[n]+1) // 2 > x:
        return count_p(n-1, x-1)
    elif (Size[n]+1) // 2 == x:
        return Patty[n-1] + 1
    else:
        return Patty[n-1] + 1 + count_p(n-1, x - ((Size[n]+1) // 2))


print(count_p(N, X))

Submission status: Accepted

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


def input(): return sys.stdin.readline().strip()


def resolve():
    N, X = map(int, input().split())
    a = [0]*N
    p = [0]*N
    a[0] = 1
    p[0] = 1
    for i in range(1, N):
        a[i] = a[i-1]*2+3
        p[i] = p[i-1]*2+1

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


resolve()

Submission status: Accepted

Solution code:
import sys
from functools import lru_cache
def input(): return sys.stdin.readline().strip()


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

    @lru_cache(maxsize=None)
    def func(n, x):
        if n == 0:
            if x <= 0: return 0
            if x >= 1: return 1
        if x >= 2 ** (n + 2) - 3:
            return func(n - 1, x) * 2 + 1
        if x >= 2 ** (n + 1) - 1:
            return func(n - 1, x) + 1 + func(n - 1, x - (2 ** (n + 1) - 1))
        if x >= 1:
            return func(n - 1, x - 1)
        return 0

    print(func(N, X))




if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def dfs(N):
    if N == 0:
        return 1
    component = dfs(N-1)
    tower = 2 * component + 1 
    return tower

N, X = map(int, input().split())
ans = 0
while X > 0:
    for n in range(0, N+1):
        if X < 2**(n+3) - 3 + (N-(n+1)):
            if X > 2**(n+2) - 3 + (N-n):
                ans += dfs(n) + 1 
                X -= 2**(n+2) - 3 + (N-n) + 1
                N = n
            else:
                if n == 0 and X <= N:
                    X = 0
                else:
                    ans += dfs(n)
                    X -= 2**(n+2) - 3 + (N-n)
                    N = n
            break

print(ans)

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
ans = 0
 
hambargers = [1]
patties = [1]
 
for i in range(1, n+1):
    num = hambargers[i-1] * 2 + 3
    patty_num = patties[i-1] * 2 + 1
    hambargers.append(num)
    patties.append(patty_num)
 
def cal(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + hambargers[N-1]:
        return cal(N-1, X-1)
    else:
        return patties[N-1] + 1 + cal(N-1, X-2-hambargers[N-1])
 
print(cal(n, x))

Submission status: Accepted

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

hambargers = [1]
patties = [1]

for i in range(1, n+1):
    num = hambargers[i-1] * 2 + 3
    patty_num = patties[i-1] * 2 + 1
    hambargers.append(num)
    patties.append(patty_num)

def cal(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + hambargers[N-1]:
        return cal(N-1, X-1)
    else:
        return patties[N-1] + 1 + cal(N-1, X-2-hambargers[N-1])

print(cal(n, x))

Submission status: Accepted

Solution code:
# D - Christmas
import sys
sys.setrecursionlimit(10**7)

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

burger = [[0, 0] for _ in range(N)]
burger[0] = [1, 1]

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

ans = 0
while True:
    if N == 0:
        if X > 0:
            ans += 1
        break
    if X > burger[N-1][0]+2:
        ans += burger[N-1][1] + 1
        X -= burger[N-1][0]+2
        N -= 1
    elif X == burger[N-1][0]+2:
        ans += burger[N-1][1] + 1
        break
    elif X < burger[N-1][0]+2:
        X -= 1
        N -= 1
print(ans)

Submission status: Accepted

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

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

#print(a)
#print(p)

ans = 0
lv = n
tmp =x
while lv >= 0:
    z = (a[lv]-1)//2
    #print('lv,tmp,z,ans: ',lv, tmp, z, ans)
    if lv == 0:
        if tmp >= 1:
            ans += 1
        break
    if tmp > z:
        ans += p[lv - 1] + 1
        tmp = tmp - z - 1
        lv -= 1
    elif tmp == z:
        ans += p[lv - 1]
        break
    else:
        tmp -= 1
        lv -= 1
        # ans 何もしない
    
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import copy
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

layers = [1] * 51
patties = [1] * 51
for i in range(1, 51):
    # レベルiバーガーの総枚数、パティの数を計算
    layers[i] = 3 + layers[i - 1] * 2
    patties[i] = 1 + patties[i - 1] * 2


def count_patties(l, x):
    # レベル0バーガーなら
    if l == 0 and x == 1:
        return 1
    # レベル0以外の場合、x <= 1なら
    if x <= 1:
        return 0
    y = layers[l - 1]
    # もしB(レベルl - 1バーガー)P(レベルl - 1バーガー)B
    #             ↑
    # にxがあれば
    if x <= y + 1:
        # 左端の一枚を除いて
        return count_patties(l-1, max(x - 1, 0))
    else:
        # 一枚目のl - 1バーガーの内部に                # 2枚目のl - 1バーガーのパティの数 + 中央の1枚
        return count_patties(l-1, min(x-y-2, y)) + patties[l-1] + 1

N, X = getNM()
print(count_patties(N, X))

Submission status: Accepted

Solution code:
#dpでできないかな？
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, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

a,x=MI()
size=[0 for i in range(a+1)]
size[0]=1
for i in range(a):
    size[i+1]=size[i]*2+3
#print(size)
#print(size[1])
patty=[0 for i in range(a+1)]
patty[0]=1
for i in range(a):
    patty[i+1]=2*patty[i]+1

def porb(k,n):
    if k==1 and n==0:
        return 1
    elif k==1:
        return 0
    elif k==size[n]:
        return patty[n]
    elif k>(size[n]+1)//2:
        return patty[n-1]+1+porb(k-(size[n]+1)//2,n-1)
    elif k==(size[n]+1)//2:
        return patty[n-1]+1
    else:
        return porb(k-1,n-1)

print(porb(x,a))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
def main():
    N, X = (int(_) for _ in input().split())

    ex2 = []
    num = 1
    for i in range(51):
        ex2.append(num)
        num *= 2

    def Height(L):
        return 4 * ex2[L] - 3

    def TotalPatty(L):
        return 2 * ex2[L] - 1

    def NumPatty(L, x):
        M = Height(L)
        m = (M+1)//2
        if x == 1:
            if L == 0: return 1
            else: return 0
        elif x == m: return TotalPatty(L-1) + 1
        elif x == M: return 2*TotalPatty(L-1) + 1
        elif 1 < x < m: return NumPatty(L-1, x-1)
        else: return TotalPatty(L-1) + 1 + NumPatty(L-1, x-(Height(L-1)+2))

    print(NumPatty(N, X))
    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, x = Is()
Blen = [0]*(n+1)
P = [0]*(n+1)
Blen[0] = 1
P[0] = 1
for i in range(1, n):
    Blen[i] = Blen[i-1]*2 + 3
    P[i] = P[i-1]*2 + 1
def burger(i, y):
    if i == 0:
        return 0 if y <= 0 else 1
    if y <= Blen[i-1] + 1:
        return burger(i-1, y-1)
    else:
        return P[i-1] + 1 + burger(i-1, y-Blen[i-1]-2)
print(burger(n, x))

Submission status: Accepted

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

layer_size = [1]
P_cnt = [1]

for _ in range(50):
  #[-1]は末尾の要素を取得。layer_sizeで、合計
  layer_size.append(layer_size[-1]*2+3)

  #[-1]は末尾の要素を取得。P_cntはパティの枚数
  P_cnt.append(P_cnt[-1]*2+1)


def solve(level, x):
  if x == 1:
    return 0 if level > 0 else 1
  l = layer_size[level-1]
  p = P_cnt[level-1]
  if x <= 1+l:
    return solve(level-1, x-1)
  elif x == l+2:
    return p+1
  elif x <= 2*l+2:
    return p+1+solve(level-1, x-l-2)
  else:
    return 2*p+1
  
ans = solve(N, X)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def f(n,x):#レベルnのx番目
    if n==0:return 0 if x<=0 else 1
    if x<=1+A[n-1]:return f(n-1,x-1)
    return 1+P[n-1]+f(n-1,x-A[n-1]-2)
def main():
    n,x=map(int,input().split())
    global A,P
    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]
    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]
    print(f(n,x))

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline

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

def S(n):
    return 2**(n+2)-3
def P(n):
    return 2**(n+1)-1

def count(n,x):
    if n == 0:
        return P(0)
    else:
        if x == 1:
            return 0
        if 1 < x <= S(n-1)+1:
            return count(n-1,x-1) 
        if x == S(n-1)+2:
            return 1 + count(n-1,x-2)
        if S(n-1)+2 < x <= 2*S(n-1)+2:
            return P(n-1) + 1 + count(n-1,x-2-S(n-1))
        else:
            return P(n-1) + 1 + count(n-1,x-3-S(n-1))

print(count(N,X))

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, x = mi()

    def calc_patty(level, num):
        '''
        level バーガーを下から num 枚食べる時に何枚パティを食べられるか計算し返す
        '''
        # 全部食べる時
        if pow(2, level + 2) - 3 == num:
            return pow(2, level + 1) - 1
        # 部分的に食べる時
        if num == 1:
            return 0
        elif num <= pow(2, level + 1) - 2:
            return calc_patty(level - 1, num - 1)
        elif num == pow(2, level + 1) - 1:
            return 1 + calc_patty(level - 1, num - 2)
        elif num <=  pow(2, level + 2) - 4:
            return calc_patty(level-1, pow(2, level+1)-3) + 1 + calc_patty(level-1, num - (pow(2, level + 1) - 1))
        else:
            raise RuntimeError
    print(calc_patty(n, x))

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,x = map(int,input().split())
a_list = [1]
p_list = [1]
for i in range(n):
  a_list.append(a_list[-1] * 2 + 3)
  p_list.append(p_list[-1] * 2 + 1)
def dfs(n,x):
  if x == 1:
    return 0
  if n == 1:
    if x ==2:
      return 1
    if x == 3 :
      return 2
    if x == 4 or x == 5:
      return 3
  elif 1 < x  and x <= a_list[n-1] +1:
    return dfs(n-1,x-1)
  elif x == a_list[n-1] + 2:
    return p_list[n-1] + 1
  elif a_list[n-1] + 2 < x and x <= 2 * a_list[n-1] + 2:
    return p_list[n-1] + 1 + dfs(n-1,x - (a_list[n-1] + 2))
  elif x == 2 * a_list[n-1] + 3:
    return 2 * p_list[n-1] + 1

print(dfs(n,x))

Submission status: Accepted

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

lengthOfBurger = [1]
numberOfPadi = [1]

for i in range(50):
    lengthOfBurger.append(1 + lengthOfBurger[-1] + 1 + lengthOfBurger[-1] + 1)
    numberOfPadi.append(numberOfPadi[-1] + 1 + numberOfPadi[-1])
A = []
def solution(k, end):
    if end == 0:
        A.append(0)
        return 0
    if end == lengthOfBurger[k]:
        A.append(numberOfPadi[k])
        return 0
    elif end == lengthOfBurger[k] + 1:
        A.append(numberOfPadi[k] + 1)
        return 0
    if end <= lengthOfBurger[k - 1] + 1:
        return solution(k - 1, end - 1)
    elif end <= lengthOfBurger[k - 1] + 2:
        return solution(k - 1, end - 1)
    elif end <= 2 * lengthOfBurger[k - 1] + 3:
        return solution(k - 1, lengthOfBurger[k - 1]+1) + solution(k - 1, end - 2 - lengthOfBurger[k - 1])
    else:
        print("NG")
        return -1

solution(n, x)

print(sum(A))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    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 solve(n, x):
        if n == 0:
            return 1 if x == 1 else 0

        if x < 2:
            return 0

        if a[n] - 1 <= x:
            return p[n]

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

    print(solve(n, x))


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

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

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

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

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

num = f(n)

ans = 0
while True:
	if num < 10 ** 5:
		break
	tmp = num // 2 + 1

	if x > tmp:
		ans += p(n) // 2 + 1
		x -= tmp
		num -= tmp + 1
	elif x < tmp:
		num -= tmp + 1
		x -= 1
	else:
		print(p(n-1)+1)
		sys.exit()
	n -= 1

string = f2(n)
if len(string) <= x:
	print(p(n)+ans)
else:
	for i in range(x):
		if string[i] == 'P':
			ans += 1
	print(ans)

Submission status: Accepted

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

level = [1]
p = [1]
for i in range(n):
    level.append(level[i]*2 + 3)
    p.append(p[i]*2 + 1)
#print(level)
#print(p)


def f(N, X):
    # 終了条件
    if N == 0:
        if X <= 0:
            return 0
        else:
            return 1
    mid = (level[N]+1)//2
    if X < mid:
        return f(N-1, X-1)
    elif X == mid:
        return p[N-1] + 1
    elif mid < X:
        return p[N-1] + 1 + f(N-1, X-mid)


ans = f(n, x)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
table = [None] * (N + 1)
table[0] = (1, 1)


def check_X(x, p):
    if x >= X:
        print(p)
        exit()


def dfs(n, x, p):
    check_X(x, p)
    if table[n] is None or x + table[n][0] > X:
        # バン
        new_x, new_p = x + 1, p

        # L-1バーガー
        new_x, new_p = dfs(n - 1, new_x, new_p)
        check_X(new_x, new_p)

        # パティ
        new_x += 1
        new_p += 1

        # L-1バーガー
        new_x, new_p = dfs(n - 1, new_x, new_p)

        # バン
        new_x += 1
        check_X(new_x, new_p)

        table[n] = (new_x - x, new_p - p)
        return new_x, new_p
    else:
        dx, dp = table[n]
        return x + dx, p + dp


dfs(N, 0, 0)

Submission status: Accepted

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

def F(N, X):
  if N == 0:
    if X > 0:
      return 1
    else:
      return 0

  if X == 1:
    return 0

  if 1 < X <= a[N-1] + 1:
    return F(N-1, X-1)

  if X ==  a[N-1] + 2:
    return b[N-1] + 1

  if a[N-1] + 2 < X <= 2*a[N-1] + 2:
    return b[N-1] + 1 + F(N-1, X - 2 - a[N-1])

  if X == 2 * a[N-1] + 3:
    return 2 * b[N-1] + 1

print(F(N, X))

Submission status: Accepted

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

N, X = map(int, readline().rstrip().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:
        if X <= 0:
            return 0
        else:
            return 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])

def main():
    print(f(N, X))

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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 x==0:
        return 0
    elif x==1:
        if n==0:
            return 1
        else:
            return 0

    elif 1<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<=2+2*a[n-1]:
        return p[n-1]+1+f(n-1,x-2-a[n-1])

    else:
        return 2*p[n-1]+1

print(f(n,x))

Submission status: Accepted

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


def solve(N: int, X: int):
    # a_0 = 1
    # a_{n+1} = 2 * a_n + 3
    # b_0 = 1
    # b_{n+1} = 2 * b_n + 1

    # a_n = 2**(n+2) - 3
    # b_n = 2**(n+1) - 1
    def f(N: int, X: int):
        aN = 2 ** (N + 2) - 3
        bN = 2 ** (N + 1) - 1
        if X >= aN:
            return bN

        aN1 = 2 ** ((N - 1) + 2) - 3

        ans = 0

        X -= 1
        if X <= 0:
            return ans

        ans += f(N - 1, X)
        X -= aN1
        if X <= 0:
            return ans

        ans += 1
        X -= 1
        if X <= 0:
            return ans

        ans += f(N - 1, X)
        X -= aN1
        if X <= 0:
            return ans

        X -= 1
        if X <= 0:
            return ans

        assert False

    print(f(N, X))


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)


if __name__ == '__main__':
    main()

Submission status: Accepted

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