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, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
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 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, X = MAP()

p = [0]*(N+1) #レベルNバーガーのパティ枚数
p[0] = 1
q = [0]*(N+1) #レベルNバーガーの総枚数
q[0] = 1

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

ans = 0
i = N
while 0 < X:
	while 0 < X < q[i]:
		i -= 1
		X -= 1
	if 0 < X:
		X -= q[i]
		ans += p[i]
	if 0 < X:
		X -= 1
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
def main():
    N, X = map(int, input().split())
    nums = [None] * (N+1)# nums[i]: i次元バーガーの層の数
    pnums = [None] * (N+1)# pnums[i]: i次元バーガーのパティの枚数
    nums[0] = 1
    pnums[0] = 1
    for i in range(N):
        nums[i+1] = nums[i]*2 + 3
        pnums[i+1] = pnums[i]*2 + 1
    
    ans = 0
    while N >= 0:
        if N == 0:
            print(ans+1)
            break
        if X == 1:
            print(ans)
            break
        elif X <= nums[N-1]+1:# N-1次元バーガの中をさらに探索
            X -= 1
            N -= 1
        elif X == nums[N-1]+2:# ぴったり真ん中のパティまで到達
            print(ans+pnums[N-1]+1)
            break
        elif X < nums[N]:
            X -= nums[N-1]+2
            ans += pnums[N-1]+1
            N -= 1
        else:
            print(ans+pnums[N])
            break
    # print(N,X)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def burger(n):#n次元バーガー出力(使わない)
    if n ==0:
        return "P"
    else:
        return "B" + burger(n-1) + "P" + burger(n-1) + "B"

def burger_size(n):#n次元バーガーのサイズ
    return 4*pow(2,n) - 3

def countP(n,x):#n次元バーガーのx層までのPの数を数えるよ
    if x <= 0:#一つも食わないとき
        return 0
    if burger_size(n)<=x:#全部食ったとき
        return 2*pow(2,n)-1
    else:
        return (1 if 2+burger_size(n-1)<=x else 0)+countP(n-1,x-1)+countP(n-1,x-2-burger_size(n-1))

print(countP(N,X))

Submission status: Accepted

Solution code:
import collections
n,x = map(int, raw_input().split(' '))
x-=1
mem = {}
def compute(n):
	if n in mem:
		return mem[n]
	if n == 0:
		return (1,1)
	else:
		h,p = compute(n-1)
		return (2*h + 3, 2*p + 1) 	
def iot(n,x,r,h):
	if h[0] > x: return
	if n == 0:
		h[0] += 1
		r[0] += 1
		return
	h[0] += 1
	if h[0] > x: return
	
	if h[0] + compute(n-1)[0] <= x:
		hh,pp = compute(n-1)
		h[0] += hh
		r[0] += pp
	else:
		iot(n-1, x, r, h)
	if h[0] > x: return
	
	h[0] += 1
	r[0] += 1

	if h[0] > x: return
	
	if h[0] + compute(n-1)[0] <= x:
		hh,pp = compute(n-1)
		h[0] += hh
		r[0] += pp
	else:
		iot(n-1, x, r, h)
	
	
	if h[0] > x: return
	
	h[0] +=1		
r,h = [0],[0]
iot(n,x,r,h)
print r[0]

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
a=[1]#層の数 a[n]はレベルnのときの層の数
p=[1]#パテの数　p[n]はレベルnのときのパテの数
for i in range(n):
    a.append(2*a[-1]+3)
    p.append(a[-1]//2 +1)
#print(a,p)
def f(n,x):
    #print(n,x)
    if n==0:
        if x>=1:
            return 1
        else:
            return 0
    elif x==1:
        return 0
    elif x==a[n]:#レベルn全部取る場合
        return p[n]
    elif x==a[n-1]+2:#レベルnの真ん中まで取る場合
        return p[n-1]+1
    elif 1<x<a[n-1]+2:
        return f(n-1,x-1)#再帰関数。行列の2番目～真ん中の1個手前まで、つまりレベルn-1バーガーに移行。レベルnバーガーの最初は飛ばすので、xも-1する。
    else:
        return p[n-1]+1+f(n-1,x-a[n-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:
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(a, p)

def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= a[N-1]+1:
        #端のバンズを消すのでXから1引く
        return f(N-1, X-1)
    else:
        #N-1層のパティ数＋真ん中のパティ＋... X-2-a[i]は追加したBPと下側のN-1層の分を引く
        return p[N-1]+1+f(N-1, X-2-a[N-1])
print(f(N, X))

Submission status: Accepted

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

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,X=mi()

    def solve(n,x):
        # print(n,x)
        if n == 0: return 1
        c = 2**(n+2)-3
        half = c//2

        res = 0
        if x <= half:
            if x == 1:
                res += 0
            else:
                res += solve(n-1,x-1)
        elif x == half+1:
            res += 2**(n-1+1) - 1 + 1
        elif x < c:
            res += 2**(n-1+1) - 1 + 1 + solve(n-1,x-(half+1))
        else:
            assert x == c
            res += 2**(n+1)-1

        return res

    print(solve(N,X))



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc115
# 10:59 giveup


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

    p = [None] * (N+1)
    p[0] = 1
    for i in range(N):
        p[i+1] = 2*p[i] + 1

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

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

        if X <= 1:
            return 0

        elif X <= 1 + whole[N-1]:
            return rec(N-1, X-1)

        elif X <= 1 + whole[N-1] + 1:
            return p[N-1] + 1

        elif X <= 1 + whole[N-1] + 1 + whole[N-1]:
            return p[N-1] + 1 + rec(N-1, X-(1+whole[N-1]+1))

        else:
            return p[N-1] + 1 + p[N-1]

    ans = rec(N, X)

    return ans


print(main())

Submission status: Accepted

Solution code:
#create date: 2020-07-01 09:01

import sys
stdin = sys.stdin
from functools import lru_cache

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

@lru_cache(maxsize=2**52-3)
def f(n, x):
    if n == 0:
        return 1

    if x == 1:
        return 0
    elif x <= 2**(n+1)-2:
        #print("f({}, {})".format(n-1, x-1))
        return f(n-1, x-1)
    elif x == 2**(n+1)-1:
        return f(n-1, 2**(n+1)-3) + 1
    elif x < 2**(n+2)-2:
        return f(n-1, 2**(n+1)-3) + 1 + f(n-1, x-(2**(n+1)-1))
    else:
        return 2 * f(n-1, 2**(n+1)-3) + 1

def main():
    n, x = na()
    print(f(n, x))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def rec(N,X):
    if N==0:
        return 1
    if X==0:
        return 0
    if 1<=X and X<=a[N-1]:
        return rec(N-1,X-1)
    if X==a[N-1]+1:
        return p[N-1]+1
    if a[N-1]+1<X:
        return rec(N-1,X-a[N-1]-2)+p[N-1]+1

N,X=map(int,input().split())
A,P=1,1
a,p=[],[]
for i in range(51):
    a.append(A);p.append(P)
    A=A*2+3;P=P*2+1
print(rec(N,X-1))

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')

sys.setrecursionlimit(100000)

N, X = in_nn()

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

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


def count(L, X):

    if L == 0:
        return 1

    if X == 1:
        return 0

    ret = 0
    if X <= blen[L] // 2:
        ret += count(L - 1, X - 1)
    else:
        ret += pcount[L - 1] + 1
        if X > blen[L] // 2 + 1:
            X -= blen[L] // 2 + 1
            X = min(X, blen[L - 1])
            ret += count(L - 1, X)

    return ret


def main():

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

total_ls = [1]
pati_ls = [1]

for i in range(50):
    total_ls.append(3 + 2 * total_ls[-1])
    pati_ls.append(1 + 2 * pati_ls[-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 cnt_p(n, x):
    if n == 0:
        if x <= 0:
            return 0
        return 1
    elif x <= 1 + a[n - 1]:
        return cnt_p(n - 1, x - 1)
    else:
        return p[n - 1] + 1 + cnt_p(n - 1, x - 2 - a[n - 1])


print(cnt_p(n, x))

Submission status: Accepted

Solution code:
def count_patties(L, x):
    if L == 0:
        return 0 if x <= 0 else 1
    if x <= total_layers[L - 1] + 1:
        return count_patties(L - 1, x - 1)
    else:
        return (
            count_patties(L - 1, x - total_layers[L - 1] - 2) + 1 + total_patties[L - 1]
        )


N, X = map(int, input().split())
total_layers = [2 ** (i + 2) - 3 for i in range(51)]
total_patties = [2 ** (i + 1) - 1 for i in range(51)]
print(count_patties(N, X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def f(N,X):
    if N==0:
        return 0 if X<=0 else 1 #レベル0バーガーはパティ1枚
    elif X<=1+a[N-1]: #食べる枚数が半数以下の時
        return f(N-1,X-1) #次数を減らせる、一番下のバンを食べるのでXを1層減らす
    else: #下半分以上食べる時
        return p[N-1]+1+f(N-1,X-2-a[N-1]) 
        #下半分に含まれるパティの枚数+真ん中のパティ+上半分の内、食べるパティを計算
        #食べる層数Xから、下半分の層数に相当するレベルN-1バーガー、バン、パティを差し引く

N,X=map(int,input().split())
#レベル0バーガーはパティ1枚
a=[1]
p=[1]

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

print(f(N,X))

Submission status: Accepted

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


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

    a = pow(2, n + 1) - 3
    b = pow(2, n) - 1

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


print(func(N, X))

Submission status: Accepted

Solution code:
def solve(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif 1 < x < layer[n] // 2 + 1:
        return solve(n-1, x-1)
    elif x == layer[n] // 2 + 1:
        return patty[n-1] + 1
    elif layer[n] // 2 + 1 < x < layer[n]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return patty[n]


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

layer, patty = [1], [1]
for _ in range(N):
    layer.append(layer[-1] * 2 + 3)
    patty.append(patty[-1] * 2 + 1)

print(solve(N, X))

Submission status: Accepted

Solution code:
def solve(n, x):
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif 1 < x <= 1 + layer[n-1]:
        return solve(n-1, x-1)
    elif x == 2 + layer[n-1]:
        return patty[n-1] + 1
    elif 2 + layer[n-1] < x <= 2 + 2 * layer[n-1]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return 2 * patty[n-1] + 1


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

layer, patty = [1], [1]
for _ in range(N):
    layer.append(layer[-1] * 2 + 3)
    patty.append(patty[-1] * 2 + 1)

print(solve(N, X))

Submission status: Accepted

Solution code:
def solve(n, x):
    if x == 1:
        return int(n <= 0)
    elif 1 < x <= 1 + layer[n-1]:
        return solve(n-1, x-1)
    elif x == 2 + layer[n-1]:
        return patty[n-1] + 1
    elif 2 + layer[n-1] < x <= 2 + 2 * layer[n-1]:
        return solve(n-1, x-layer[n-1]-2) + patty[n-1] + 1
    else:
        return 2 * patty[n-1] + 1


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

layer, patty = [1], [1]
for _ in range(N):
    layer.append(layer[-1] * 2 + 3)
    patty.append(patty[-1] * 2 + 1)

print(solve(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[i]+3)
    p.append(2*p[i]+1)
def f(n,x):
    if x == 1:
        return int(n <= 0)
    elif 1 < x <= a[n-1]+1:
        return f(n-1,x-1)
    elif x == 2 + a[n-1]:
        return 1+p[n-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])
    elif x == 2*a[n-1]+3:
        return 2*p[n-1]+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+=[a[i]*2+3]; p+=[p[i]*2+1]
def f(n,x):
  return int(x>0) if n<1 else p[n-1]+1+f(n-1,x-2-a[n-1]) if x>a[n]//2 else f(n-1,x-1)
print(f(n,x))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[1]
for i in range(50): l+=[l[-1]*2+3]
from functools import lru_cache
@lru_cache(None)
def f(n,x):
  return int(x>0) if n<1 else f(n-1,l[n-1])+1+f(n-1,x-l[n-1]-2) if x>l[n]//2 else f(n-1,x-1)
print(f(n,x))

Submission status: Accepted

Solution code:
n,x=map(int,input().split())
l=[1]
for i in range(50): l+=[l[-1]*2+3]
from functools import lru_cache
@lru_cache(None)
def f(n,x):
  if n<1: return int(x>0)
  if x<=l[n]//2: return f(n-1,x-1)
  return f(n-1,l[n-1])+1+f(n-1,x-l[n-1]-2)
print(f(n,x))

Submission status: Accepted

Solution code:
nn,xx=map(int,input().split())
def f(n,x):
  if x==0:
    return 0
  if n==0:
    return 1
  if x==2**(n+2)-3:
    return 2**(n+1)-1
  b=2**(n+1)-3
  u=min(b,max(0,x-2-b))
  l=min(x-1,b)
  return f(n-1,u)+(1 if x>b+1 else 0)+f(n-1,l)
print(f(nn,xx))

Submission status: Accepted

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

def cnt(n,x):
	if n==0 and x<=0:
		return 0
	if n==0 and x>=1:
		return 1
	m=(B[n]+1)//2
	if x<m:
		return cnt(n-1,x-1)
	elif x==m:
		return P[n-1]+1
	elif x>m:
		return P[n-1]+1+cnt(n-1, x-m) 

print(cnt(n,x))

Submission status: Accepted

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

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

ans = 0
#print(An, Pn)

def f(x, i):
  global ans

  if x == An[i]:
    ans += Pn[i]
    print(ans)

  elif An[i]//2 + 1 < x < An[i]:
    ans += Pn[i-1] + 1
    f(x-(An[i]//2 + 1), i-1)

  elif An[i]//2 + 1 == x:
    ans += Pn[i-1] + 1
    print(ans)

  elif 1 < x <= An[i]//2:
    f(x-1, i-1)

  else:
    print(ans)

f(X, N)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n , x = map(int, input().split())
l = 2**(n+2)-3

ans = 0
k=n
while l>=1:
    if x==(l+1)//2:
        ans+=2**(k)
        break
    if x==(l+1)//2-1:
        ans+=2**(k)-1
        break
    if x>(l+1)//2:
        ans+=2**(k)
        x-=(l+1)//2-1
    k-=1
    x-=1
    l=(l-1)//2-1
print(ans)

Submission status: Accepted

Solution code:
from functools import lru_cache
n, x = map(int, input().split())

@lru_cache(None)
def d(k):
    if k == 0:
        return 1
    return 2 * d(k-1) + 3

@lru_cache(None)
def f(i, h):
    if h == 0:
        return i
    rv = 0
    if i >= 1:
        rv += f(min(i-1, d(h-1)), h-1)
    if i >= d(h-1) + 2:
        rv += 1 + f(min(i - d(h-1) - 2, d(h-1)), h-1)
    return rv

print(f(x, n))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
d = [1]
for _ in range(50):
    d.append(d[-1] * 2 + 3)
ans = 0
def f(i, h):
    if h == 0:
        return 1 if i == 1 else 0
    if i == 0:
        return 0
    mid = d[h-1] + 1
    if i <= mid:
        return f(i-1, h-1)
    if i == mid + 1:
        return 2 ** h
    if i <= d[h] - 1:
        return 2 ** h + f(i-mid-1, h-1)
    else:
        return 2 ** (h + 1) - 1
print(f(x, n))

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):
    #print(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])
print(f(n,x))

Submission status: Accepted

Solution code:
# from typing import NamedTuple

# class Burger(NamedTuple):
#     total: int
#     patty: int

from collections import namedtuple

def solve(n, x, burgers, total_eaten, patty_eaten):
    if n == 0:
        total_eaten += 1
        patty_eaten += 1
        return total_eaten, patty_eaten

    # try to eat the entire current level
    tmp_total = burgers[n].total
    tmp_patty = burgers[n].patty
    if total_eaten + tmp_total < x:
        return total_eaten + tmp_total, patty_eaten + tmp_patty

    # eat the lower bun
    total_eaten += 1
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the lower n - 1 th burger
    total_eaten, patty_eaten = solve(n - 1, x, burgers, total_eaten, patty_eaten)
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the middle patty
    total_eaten += 1
    patty_eaten += 1
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the upper n - 1 th burger
    total_eaten, patty_eaten = solve(n - 1, x, burgers, total_eaten, patty_eaten)
    if total_eaten == x:
        return total_eaten, patty_eaten

    # eat the upper bun
    # the program should not reach the current line because this mean n th burger is eaten (= eat the entire current level)
    total_eaten += 1
    return total_eaten, patty_eaten

def main():
    N, X = map(int, input().split())
    Burger = namedtuple('Burger', ['total', 'patty'])
    burgers = [Burger(total=1, patty=1)]
    for i in range(N):
        total = burgers[i].total
        patty = burgers[i].patty
        burger = Burger(total=3 + total*2, patty=1 + 2*patty)
        burgers.append(burger)
    # print(burgers)
    total_eaten, patty_eaten = 0, 0
    total_eaten, patty_eaten = solve(N, X, burgers, total_eaten, patty_eaten)
    print(patty_eaten)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#import itertools
#from fractions import Fraction
#import itertools
from collections import deque
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
#import bisect
N,X=map(int,input().split())
l=[1]*(N+1)
p=[1]*(N+1)
for i in range(1,N+1):
    l[i]=2*l[i-1]+3
    p[i]=2*p[i-1]+1
def ans(n,x):
    if n==0:
        return 1
    if x==1:
        return 0
    elif 1<x<=l[n-1]+1:
        return ans(n-1,x-1)
    elif x==l[n-1]+2:
        return p[n-1]+1
    elif l[n-1]+2<x<=2*l[n-1]+2:
        return p[n-1]+1+ans(n-1,x-l[n-1]-2)
    else:
        return p[n-1]*2+1
print(ans(N,X))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)  # 再帰関数のRecursionError対策

n, x = map(int, input().split())
As = [1]  # レベルiバーガーの厚さ（層の総数）（必ず奇数）
Ps = [1]  # レベルiバーガーのパティの総数

for i in range(n):
    As.append(As[i]*2 + 3)  # レベルが1上がると、総数は2倍+3になる
    Ps.append(Ps[i]*2 + 1)  # レベルが1上がると、パティの数は2倍+1になる

def f(n, x):
    """レベルnバーガーの下からx層食べたときの、食べたパティの総数"""
    if n == 0:
        return 0 if x <= 0 else 1

    median = (As[n]+1)//2

    if x < median:
        return f(n-1, x-1)
    elif x == median:
        return Ps[n-1] + 1
    elif x > median:
        return Ps[n-1] + 1 + f(n-1, x-median)

ans = f(n, x)

print(ans)

Submission status: Accepted

Solution code:
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)
    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))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
# レベルnバーガーの下からx層に含まれるパティの枚数
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])

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(f(n,x))

Submission status: Accepted

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

for i in range(50):
    ls.append(2 * ls[-1] + 3)
    pts.append(2 * pts[-1] + 1)

ans = 0

while n > 0 and x >= 0:
    if x < ls[n]//2:
        x -= 1
        n -= 1
    elif x == ls[n]//2:
        x = -1
        ans += pts[n-1]
    else:
        if x == ls[n]:
            x = 0
            ans += pts[n]
        else:
            x -= ls[n]//2
            ans += pts[n-1]+1
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 paty(L, n):
    if L == 0:
        return 0 if n <= 0 else 1
    elif n <= 1 + a[L - 1]:
        return paty(L-1, n-1)
    else:
        return p[L-1] + 1 + paty(L-1, n-2-a[L-1])

print(paty(N, X))

Submission status: Accepted

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

def paty(L, n):
    if (L, n) in paty_list:
        return paty_list[L, n]
    ans = 0
    count = 0
    if count + 1 >= n:
        paty_list[(L, n)] = ans
        return ans
    count += 1
    if L_list[L-1] + count > n:
        ans += paty(L-1, n-count)
        paty_list[(L, n)] = ans
        return ans
    ans += paty(L-1, L_list[L-1])
    count += L_list[L-1]  
    if count + 1 > n:
        paty_list[(L, n)] = ans
        return ans
    ans += 1
    count += 1
    if L_list[L-1] + count > n:
        ans += paty(L-1, n-count)
        paty_list[(L, n)] = ans
        return ans
    ans += paty(L-1, L_list[L-1])
    paty_list[(L, n)] = ans
    return ans

print(paty(N, X))

Submission status: Accepted

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


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

whole = [1]
putty = [1]
for _ in range(50):
    whole.append(whole[-1] * 2 + 3)
    putty.append(putty[-1] * 2 + 1)


@lru_cache(maxsize=None)
def rec(n, x):
    if n == 0:
        # n == 0のとき、x <= 1なら常にパティ
        return 0 if x < 1 else 1

    # 真ん中で条件分岐する
    med = (whole[n]+1) // 2

    # 真ん中より下なら、1つ前のレベルの結果を少し改造すればよい
    if x < med:
        return rec(n - 1, x - 1)
    # 真ん中なら、1つ前のレベルのパティ総数に1つ足せばよい
    elif x == med:
        return putty[n - 1] + 1
    # 真ん中より上なら、x == medの結果に1つ前のレベルの結果を改造したものを足せばよい
    elif x > med:
        return putty[n - 1] + 1 + rec(n - 1, x - med)


ans = rec(n, x)

print(ans)

Submission status: Accepted

Solution code:
num = [1]
for i in range(1, 50):
  num.append(2 * num[i - 1] + 3)
def count_p(level, x):
  if x == 0:
    return 0
  if level == 1:
    if x == 5:
      return 3
    else:
      return x - 1
  if x < num[level - 1] + 1:
    return count_p(level - 1, x - 1)
  if x == num[level - 1] + 1:
    return 2 ** level - 1
  if x >= num[level - 1] * 2 + 2:
    return 2 ** (level + 1) - 1
  if x >= num[level - 1] + 2:
    return 2 ** level + count_p(level - 1, x - num[level - 1] - 2)


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

Submission status: Accepted

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

Submission status: Accepted

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

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)


def calc(N, X):
    if X == 1:
        if N == 0:
            return 1
        else:
            return 0
    elif X <= 1+a[N-1]:
        return calc(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+calc(N-1, X-2-a[N-1])
    elif X == 2*a[N-1]+3:
        return 2*p[N-1]+1
    else:
        raise("Error")


print(calc(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 resolve():
    N, X = list(map(int, input().split()))
    level_len = [1]
    for i in range(1, N+1):
        level_len.append(2*level_len[i-1]+3)
    #print(level_len)
    mem = {"0-0": 1}

    def get_cnt(level, pos):
        if "{}-{}".format(level, pos) in mem:
            return mem["{}-{}".format(level, pos)]

        result = None
        if pos == 0:
            result = 0
        elif 1 <= pos <= level_len[level-1]:
            result = get_cnt(level-1, pos-1)
        elif pos == 1+level_len[level-1]:
            result = get_cnt(level-1, level_len[level-1]-1)+1
        elif 1+level_len[level-1] < pos <= 1+2*level_len[level-1]:
            result = get_cnt(level-1, level_len[level-1]-1) + 1 + get_cnt(level-1, pos-level_len[level-1]-2)
        elif pos == 2*level_len[level-1]+2:
            result = 2*get_cnt(level-1, level_len[level-1]-1)+1

        if result is None:
            #print(level, pos)
            raise Exception("Invalid")
        mem.setdefault("{}-{}".format(level, pos), result)
        return result
    
    print(get_cnt(N, X-1))

    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

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

def f(lv,x):
    if lv == 0: return 1
    elif x <= 1: return 0
    elif x <= cnt[lv-1] + 1: return f(lv-1,x-1)
    elif x == cnt[lv-1] + 2: return pcnt[lv-1]+1
    elif x <= 2*cnt[lv-1] + 2: return pcnt[lv-1]+1+f(lv-1,x-cnt[lv-1]-2)
    else: return pcnt[lv]

print(f(n,x))

Submission status: Accepted

Solution code:
def do(lv, dan):
    res = 0
    #print("do({0}, {1})".format(lv, dan))
    if lv == 0:
        if dan == 0:
            return 0
        elif dan == 1:
            return 1
        else:
            print("!!!!!!!!!!!!!!!!!!!!!!!!!!")
    if dan == 0:
        return 0

    dan -= 1

    if dan == 0:
        return 0

    if burgersize[lv-1] <= dan:
        res += pnum[lv-1]
        dan -= burgersize[lv-1]
    else:
        res = do(lv-1, dan)
        dan = 0

    if dan >= 1:
        res += 1
        dan -= 1
    else:
        return res

    if burgersize[lv-1] <= dan:
        res += pnum[lv-1]
        dan -= burgersize[lv-1]
    else:
        res += do(lv-1, dan)
        dan = 0


    return res

burgersize = [1] * 51
pnum = [1] * 51
for i in range(1, 51):
    burgersize[i] = burgersize[i-1] * 2 + 3
    pnum[i] = pnum[i-1] * 2 + 1
#print(burgersize[:10])
#print(pnum[:10])
a,b = map(int, input().split())
print(do(a, b))