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: Wrong Answer

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

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


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

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

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

print(rec(N))
ans = rec(N)[-X:].count('P')
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def make_burger(n):
    patty = [None] * (n + 1)
    bun = [None] * (n + 1)
    patty[0] = 1
    bun[0] = 0
    burger = [None] * (n + 1)
    burger[0] = 1
    for i in range(n):
        patty[i+1] = patty[i] * 2 + 1
        bun[i+1] = bun[i] * 2 + 2
        burger[i+1] = patty[i+1] + bun[i+1]
    
    return patty, bun, burger

n, x = map(int, sys.stdin.readline().split())

def main():
    r = x
    patty, bun, burger = make_burger(n)

    res = 0
    for l in range(n, 0, -1):
        half_burger = burger[l] // 2 + 1
        half_patty = patty[l] // 2 + 1
        if r == 1:
            break
        elif r < half_burger:
            r -= 1
        elif r == half_burger:
            res += half_patty
            break
        elif r < burger[l]:
            res += half_patty
            r -= half_burger
        elif r == burger[l]:
            res += patty[l]
            break
    if r:
        res += 1
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys

def make_burger(n):
    patty = [None] * (n + 1)
    bun = [None] * (n + 1)
    patty[0] = 1
    bun[0] = 0
    burger = [None] * (n + 1)
    burger[0] = 1
    for i in range(n):
        patty[i+1] = patty[i] * 2 + 1
        bun[i+1] = bun[i] * 2 + 2
        burger[i+1] = patty[i+1] + bun[i+1]
    
    return patty, bun, burger

n, x = map(int, sys.stdin.readline().split())

def main():
    r = x
    patty, bun, burger = make_burger(n)

    res = 0
    for l in range(n, 0, -1):
        half_burger = burger[l] // 2 + 1
        half_patty = patty[l] // 2 + 1
        if r == 1:
            break
        elif r < half_burger:
            r -= 1
        elif r == half_burger:
            res += half_patty
            break
        elif r < burger[l]:
            res += half_patty
            r -= half_burger
        elif r == burger[l]:
            res += patty[l]
            break
    return res
    
if __name__ == '__main__':
    ans = main()
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,X=map(int,input().split())
    
    memo=[(0,0)]*N
    memo[0]=(1,1)
    for i in range(N-1):
        memo[i+1]=(memo[i][0]*2+3,memo[i][1]*2+1)
    def saiki(n,x):
        x-=1
        if n==0:
            return 1 if x>0 else 0
        if memo[n-1][0]+1<x:
            return memo[n-1][1]+saiki(n-1,x-(memo[n-1][0]+1))+1
        else:
            return saiki(n-1,x)+max(x-memo[n-1][0],0)
    print(saiki(N,X))
        

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc115/tasks/abc115_d
# 真面目に再帰関数によって文字列を生成すると、長さが爆発してしまう
# 問題の再帰構造を観察すると、二分探索のような処理でPの数を確定できる


def ret_length(L):
    ret = 1
    for _ in range(L):
        ret = 2 * ret + 3
    return ret


def ret_nP(L):
    ret = 1
    for _ in range(L):
        ret = 2 * ret + 1
    return ret


N, X = list(map(int, input().split()))
X -= 1  # X枚目まで食べるという扱いにする (0based index)

lng = ret_length(N)
nP = ret_nP(N)

# print(lng, nP)
ans = 0
l = 0
r = lng - 1
while r - l > 1:  # lrが隣り合ったら終わり
    m = (r + l) // 2  # 必ず真ん中を指す
    if r == X:
        ans += nP
        break
    elif l == X:
        break

    nP = nP // 2
    if X == m:
        ans += nP + 1
        break
    if X > m:
        # Bの数を足す
        ans += nP + 1
        l = m + 1
        r -= 1
    else:
        l += 1
        r = m - 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
def func(N,X):
    if N == 0:
        return 1
    elif X == 1:
        return 0
    elif 2 <= X <= 2**(N+1) -2:
        return func(N-1,X-1)
    elif X == 2**(N+1)-1:
        return 2**N
    elif 2**(N+1) <= X <= 2**(N+2)-4:
        return 2**N + func(N-1,X-(2**(N+1)-1))
    else:
        return 2*(2**N)+1
print(func(N,X))

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
def func(N,X):
    if N == 0:
        if X > 0:
            return 1
        else:
            return 0
    elif X == 1:
        return 0
    elif 2 <= X <= 2**(N+1) -2:
        return func(N-1,X-1)
    elif X == 2**(N+1)-1:
        return 2**N
    elif 2**(N+1) <= X <= 2**(N+2)-4:
        return 2**N + func(N-1,X-(2**(N+1)-1))
    else:
        return 2*(2**N)+1
print(func(N,X))

Submission status: Wrong Answer

Solution code:
N,X = map(int,input().split())
def func(N,X):
    if X == 1:
        return 0
    elif 2 <= X <= 2**(N+1) -2:
        return func(N-1,X-1)
    elif X == 2**(N+1)-1:
        return 2**N
    elif 2**(N+1) <= X <= 2**(N+2)-4:
        return 2**N + func(N-1,X-(2**(N+1)-1))
    else:
        return 2*(2**N)+1
print(func(N,X))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from functools import lru_cache

@lru_cache(maxsize=None)
def solve(l):
    if l == 0:
        return 1, 1
    x, y = solve(l - 1)
    return x * 2 + 1, y * 2 + 3


def main():
    N, X = [int(x) for x in input().split()]
    b = []
    for y in range(51):
        b.append(solve(y))

    # print(b)
    ans = 0
    for y in range(N, -1, -1):
        if X >= b[y][1] * 2 + 1:
            X -= b[y][1]
            X -= b[y][1]
            ans += b[y][0]
            ans += b[y][0]
            ans += 1
        elif X >= b[y][1] + 1:
            X -= b[y][1]
            ans += b[y][0]
            ans += 1
            X -= 2
        elif X >= b[y][1]:
            X -= b[y][1]
            ans += b[y][0]
        else:
            X -= 1

    if X >= 1:
        ans += 1
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

print(f(N,X))

Submission status: Wrong Answer

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 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] + f(N-1, X-2-a[N-1])
print(f(N,X))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
N, X = map(int, input().split())
ans = 0
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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, x = [int(x) for x in input().strip().split()]
burgers = [False] * (n + 1)
burgers[0] = 'p'
leng = [1] * (n + 1)
patties = [1] * (n + 1)
for i in range(1, n+1):
    leng[i] = 2 * leng[i-1] + 3
    patties[i] = 2 * patties[i-1] + 1
def burger(l, x):
    if l == 0:
        ret = 1
    elif x == 1:
        ret = 0
    elif x <= leng[l] // 2:
        ret = burger(l-1, x)
    elif x == leng[l] // 2 + 1:
        ret = burger(l-1, x-2) + 1
    elif x < leng[l] - 2:
        ret = burger(l-1, leng[l-1]) + 1 + burger(l-1, x-2-leng[l-1])
    else:
        ret = patties[l]
    #print('l = {}, x = {}, ret = {}'.format(l, x, ret))
    return ret

print(burger(n, x))

Submission status: Wrong Answer

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


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


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

Submission status: Wrong Answer

Solution code:
ri = lambda: map(int, input().split(' '))
L = [1]
C = [1]

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

	if x == L[n]:
		return 2*C[n-1] + 1

	ans = 0
	if x >= L[n-1] + 2:
		ans += C[n-1] + 1
		ans += rec(n-1, x-L[n-1]-2)
	else:
		ans += rec(n-1, x-1)

	return ans

if __name__ == '__main__':
	N, X = ri()
	for i in range(1, N+1):
		L.append(2*L[i-1] + 3)
		C.append(2*C[i-1] + 1)
	ans = rec(N, X)
	print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: map(int, input().split(' '))
L = [1]
C = [1]

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

	if x == L[n]:
		return 2*C[n-1] + 1

	ans = 0
	if x >= L[n-1] + 2:
		ans += C[n-1] + 1
		ans += rec(n-1, x-L[n-1]-2)
	else:
		ans += rec(n-1, x-1)

	return ans

if __name__ == '__main__':
	N, X = ri()
	for i in range(1, N+1):
		L.append(2*L[i-1] + 3)
		C.append(2*C[i-1] + 1)
	ans = rec(N, X)
	print(ans)

Submission status: Wrong Answer

Solution code:
ri = lambda: map(int, input().split(' '))
L = [1]
C = [1]

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

	if x == L[n]:
		return 2*C[n-1] + 1

	ans = 0
	if x >= L[n-1] + 2:
		ans += C[n-1] + 1
		ans += rec(n-1, x-L[n-1]-1)
	else:
		ans += rec(n-1, x-1)

	return ans

if __name__ == '__main__':
	N, X = ri()
	for i in range(1, N+1):
		L.append(2*L[i-1] + 3)
		C.append(2*C[i-1] + 1)
	ans = rec(N, X)
	print(ans)

Submission status: Wrong Answer

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

dp = [0] * (N + 1)
p_dp = [0] * (N + 1)
dp[0] = 1
p_dp[0] = 1
for i in range(1, N + 1):
    dp[i] = dp[i - 1] * 2 + 3
    p_dp[i] = p_dp[i - 1] * 2 + 1
patties = p_dp[N]
burger_len = dp[N]

tmp = X
middle = -(-dp[N]//2)
n = N - 1
ans = 0
while True:
    print("middle:", middle)
    print("tmp:", tmp)
    if tmp == 1:
        if middle == 1:
            ans += 1
        break
    if tmp == middle:
        ans += p_dp[n] + 1
        break
    if tmp == dp[n + 1]:
        ans += p_dp[n] * 2 + 1
        break
    if 1 < tmp < middle:
        middle = -(-dp[n]//2)
        tmp -= 1
        n -= 1
    if middle < tmp < dp[n + 1]:
        tmp -= middle
        middle = -(-dp[n]//2)
        ans += p_dp[n] + 1
        n -= 1
print(ans)

Submission status: Wrong Answer

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

dp = [0] * (N + 1)
p_dp = [0] * (N + 1)
dp[0] = 1
p_dp[0] = 1
for i in range(1, N + 1):
    dp[i] = dp[i - 1] * 2 + 3
    p_dp[i] = p_dp[i - 1] * 2 + 1
patties = p_dp[N]
burger_len = dp[N]

tmp = X
middle = -(-dp[N]//2)
n = N - 1
ans = 0
while True:
    #print(middle)
    if tmp == 1:
        break
    if tmp == middle:
        ans += p_dp[n] + 1
        break
    if tmp == dp[n + 1]:
        ans += p_dp[n] * 2 + 1
        break
    if 1 < tmp < middle:
        middle = -(-dp[n]//2)
        tmp -= 1
        n -= 1
    if middle < tmp < dp[n + 1]:
        tmp -= middle
        middle = -(-dp[n]//2)
        ans += p_dp[n] + 1
        n -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
ans=0
def rec(x,n):
    global ans
    if n==0:
        if x==1:
            ans+=1
    elif x>2**(n+1)-2:
        ans+=(2**n-1+1)
        rec(x-(2**(n+1)-1),n-1)
    else:
        rec(x-1,n-1)

rec(X,N)
print(ans)

Submission status: Wrong Answer

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

    A = [1] * (N+1)
    P = [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 X == 1:
            return 0
        elif X <= 1 + A[N-1]:
            return f(N-1, X-1)
        elif X == 2 + A[N-1]:
            return P[N-1] + 1
        elif X <= 2 + 2 * A[N-1]:
            return P[N-1] + 1 + f(N-1, X-2-A[N-1])
        elif X == 3+2*A[N-1]:
            return 2 * P[N-1] + 1

    print(f(N, X))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
L = [4 * (2 ** i) - 3 for i in range(51)]
P = [2 * (2 ** i) - 1 for i in range(51)]
N, X = map(int, input().split())
def solve(level, x):
  print(level, x, file=sys.stderr)
  if x <= 1:
    return 0
  elif x >= L[level-1] + 2:
    return P[level-1] + 1 + solve(level-1, x - L[level-1] - 2)
  else:
    return solve(level-1, x-1)
print(solve(N, X))

Submission status: Wrong Answer

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

def paty(n,x):
  #print('n:{}'.format(n))
  #print('x:{}'.format(x))
  if n == 0:
    if x == 1:
      return 1
    else:
      return 0
  elif int((2**(n+2)-3 - 1) / 2) >= x:
    return paty(n-1,x-1)
  elif int((2**(n+2)-3 + 1) / 2) == x:
    return paty(n-1,x-2) + 1
  elif (2**(n+2)-3) - 1 <= x:
    return 2*paty(n-1, x-(2**(n+1)-3) -2) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    elif x == 0:
      return 0
  elif n == 1:
    if x == 5:
      return 3
    else:
      return x - 1
  elif int((2**(n+2)-3 - 1) / 2) >= x:
    return paty(n-1,x-1)
  elif int((2**(n+2)-3 + 1) / 2) == x:
    return paty(n-1,x-2) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    elif x == 0:
      return 0
  elif n == 1:
    if x == 1:
      return 0
    elif x == 5:
      return 3
    else:
      return x - 1
  elif int((2**(n+2)-3 - 1) / 2) >= x:
    return paty(n-1,x-2)
  elif int((2**(n+2)-3 + 1) / 2) == x:
    return paty(n-1,x-2) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    else:
      return 0
  elif int((2**(n+2)-3 - 1) / 2) >= x:
    return paty(n-1,x-1)
  elif int((2**(n+2)-3 + 1) / 2) == x:
    return paty(n-1,x-1) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    else:
      return 0
  elif int((2**(n+2)-3 + 1) / 2) >= x:
    return paty(n-1,x-1) + 1
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

def paty(n,x):
  if n == 0:
    if x == 1:
      return 1
    else:
      return 0
  elif int((2**(n+2)-3 + 1) / 2) >= x:
    return paty(n-1,x-1)
  else:
    return 2**n + paty(n-1, x-(2**(n+1)-3) -2)
  
ans = paty(N,X)
print(ans)

Submission status: Wrong Answer

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

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)
ans = patty(n,x)
print(ans)

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
S = 0
M = 2 ** (N + 2) - 3
P = 2 ** (N + 1) - 1
for i in range(N):
  P -= 1
  P //= 2
  M -= 1
  M //= 2
  if X - 1 == M:
    S += 1 + P
    break
  elif X - 1 == 2 * M:
    S += 1 + 2 * P
    break
  elif X - 1 == 0:
    break
  elif (X - 1) % M != 0 and (X - 1) > M:
    S += 1 + P
    X -= M + 1
    M -= 1
  elif (X - 1) % M != 0 and (X - 1) < M:
    X -= 1
    M -= 1
print(S)

Submission status: Wrong Answer

Solution code:
L, X=map(int, input().split())
def h(l):
  if l==0:
    return 1
  else:
    return h(l-1)*2+3

def f(l,x):
  if l == 0:
    if x == 0:
      return 0
    else:
      return 1
  else:
    if x <= 1:
      return 0
    elif x <= h(l-1) + 1:
      return f(l-1, x)
    elif x == h(l-1) + 2:
      return f(l-1, h(l-1))+1
    elif x <= h(l-1) * 2 + 2:
      return f(l-1, h(l-1))+1+f(l-1, x - h(l-1) - 2 )
    else:
      return f(l-1, h(l-1)) * 2 + 1
print(f(L,X))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
A=[0]*51
B=[0]*51
A[0]=1
B[0]=1
i=1
while i<=50:
  A[i]=A[i-1]*2+3
  B[i]=B[i-1]*2+1
  i=i+1
#print(A)
#print(A[50])
#print(B[50])
ans=0
for i in range(n-1,0,-1):
  #print(i)
  if x==1 or x==0:
    break
  elif 1<x and x<=1+A[i]:
    x=x-1
  elif x==2+A[i]:
    ans=ans+B[i]+1
    break
  elif 2+A[i]<x and x<A[i+1]:
    ans=ans+B[i]+1
    x=x-A[i]-2
  else:
    ans=ans+2*B[i]+1
    break
  if i==1:
    if x==2:
      ans=ans+1
    elif x==3:
      ans=ans+2
    elif x==4 or x==5:
      ans=ans+3
print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
def make_burger():
    global burger_before
    global burger_after
    burger_before = burger_after
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    
    
N,X = map(int,input().split())
burger_before = "P"
burger_after = ""

for i in range(1,N+1):
    make_burger()

eat = burger_after[-X:]
#print(burger_after)
print(eat.count("P"))

Submission status: Wrong Answer

Solution code:
def make_burger():
    global burger_before
    global burger_after
    burger_before = burger_after
    burger_after = "B" + burger_before + "P" + burger_before + "B"
    
    
N,X = map(int,input().split())
burger_before = "P"
burger_after = ""

for i in range(1,N+1):
    make_burger()

eat = burger_after[-X:]
print(burger_after)
print(eat.count("P"))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
#N=2
#M=7

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

for i in range (1,N+1):
    MEMO[i][0]=MEMO[i-1][0]*2+3
    MEMO[i][1]=MEMO[i-1][1]*2+1
t=1
s=0
n=N-1
while(True):
    if(t==M):break
    if(t+MEMO[n][0]<M):
        t=t+MEMO[n][0]+1
        s+=MEMO[n][1]+1
    elif(t+MEMO[n][0]>M):
        t+=1
        n-=1
    else:
        s+=MEMO[n][1]
print(s)

Submission status: Wrong Answer

Solution code:
N,X=map(int,input().split())
Thick=[]
P=[]
a=1
b=1
for i in range(N+1):
  Thick.append(a)
  P.append(b)
  a=a*2+3
  b=b*2+1
def dfs(l,x):
  if l==0:
    return 1
  
  if x==1:
    return 0
  elif x==Thick[l]//2:
    return P[l-1]
  elif x==Thick[l]//2+1:
    return P[l-1]+1
  elif x==Thick[l]:
    return P[l-1]*2
  else:
    if x<Thick[l]//2:
      return dfs(l-1,x-1)
    else:
      return P[l-1]+1+dfs(l-1,x-(Thick[l]//2+1))

print(dfs(N,X))

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,x = [int(x) for x in stdin.readline().rstrip().split()]
p = [1]
t = [1]
for i in range(n):
    p.append(p[i]*2+1)
    t.append(t[i]*2+3)

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

print(f(n,x))

Submission status: Wrong Answer

Solution code:
from sys import stdin

n,x = [int(x) for x in stdin.readline().rstrip().split()]
p = [1]
t = [1]
for i in range(1,n):
    p.append(p[i-1]*2+1)
    t.append(t[i-1]*2+3)

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

print(f(n,x))

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
A=[0]*51
B=[0]*51
A[0]=1
B[0]=1
i=1
while i<=50:
  A[i]=A[i-1]*2+3
  B[i]=B[i-1]*2+1
  i=i+1
#print(A)
#print(A[50])
#print(B[50])
ans=0
for i in range(n-1,-1,-1):
  #print(i)
  if x==1 or x==0:
    break
  elif 1<x and x<=1+A[i]:
    x=x-1
  elif x==2+A[i]:
    ans=ans+B[i]+1
    break
  elif 2+A[i]<x and x<A[i+1]:
    ans=ans+B[i]+1
    x=x-A[i]-2
  else:
    ans=ans+2*B[i]+1
    break
print(ans)

Submission status: Wrong Answer

Solution code:
n,x=map(int,input().split())
A=[0]*51
B=[0]*51
A[0]=1
B[0]=1
i=1
while i<=50:
  A[i]=A[i-1]*2+3
  B[i]=B[i-1]*2+1
  i=i+1
#print(A)
#print(A[50])
#print(B[50])
ans=0
for i in range(n-1,-1,-1):
  #print(i)
  if x==1:
    break
  elif 1<x and x<1+A[i]:
    x=x-1
    continue
  elif x==2+A[i]:
    ans=ans+B[i]+1
    break
  elif 2+A[i]<x and x<A[i+1]:
    ans=ans+B[i]+1
    x=x-A[i]-2
    continue
  else:
    ans=ans+2*B[i]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def thk(n):
    return 2**(n+2)-3
def pt(n):
    return 2**(n+1)-1
def ban(n):
    return 2**(n+1)-2

N,X = map(int, input().split(' '))
ans = 0

for i in range(50):
    if X == 0:
        break
    elif X == thk(N)//2+1:
        ans += pt(N-1)+1
        break
    elif X == thk(N):
        ans += 2*pt(N-1)+1
        break
    elif X > thk(N)//2+1:
        ans += pt(N-1)+1
        X -= thk(N)//2+1
        N -= 1
    else:
        X -= 1
        N -= 1

print(ans)

Submission status: Wrong Answer

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

# 層の総数
T = [1]
for i in range(1, 50+1):
    T.append(T[i-1]*2+3)

def hash(n,x):
    return "{0:d},{1:d}".format(n,x)

# レベルnバーガーの下からx層内のパティの数
memo = dict()
def solve(n,x):
    global T, memo
    if hash(n,x) in memo:
        return memo[hash(n,x)]
    if n == 0 and x >= 1:
        memo[hash(n,x)] = 1
        return 1
    if x <= 1:
        memo[hash(n,x)] = 0
        return 0
    memo[hash(n,x)] = solve(n-1, min(x-1, T[n-1]))
    if x >= T[n-1]+1:
        memo[hash(n,x)] += 1
    if x >= T[n-1]+2:
        memo[hash(n,x)] += solve(n-1, min(x-1-T[n-1]-1, T[n-1]))
    return memo[hash(n,x)]

print(solve(N,X))

Submission status: Wrong Answer

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

# 層の総数
T = [1]
for i in range(1, 50+1):
    T.append(T[i-1]*2+3)

def hash(n,x):
    return "{0:d},{1:d}".format(n,x)

# レベルnバーガーの下からx層内のパティの数
memo = dict()
def solve(n,x):
    global T, memo
    if hash(n,x) in memo:
        return memo[hash(n,x)]
    if n == 0:
        memo[hash(n,x)] = 1
        return 1
    if x <= 1:
        memo[hash(n,x)] = 0
        return 0
    memo[hash(n,x)] = solve(n-1, min(x-1, T[n-1]))
    if x >= T[n-1]+1:
        memo[hash(n,x)] += 1
    if x >= T[n-1]+2:
        memo[hash(n,x)] += solve(n-1, min(x-1-T[n-1]-1, T[n-1]))
    return memo[hash(n,x)]

print(solve(N,X))

Submission status: Wrong Answer

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)
print(A,P)

def func(n,x):
	if x <= 0:
		return 1
	elif x == 1:
		return 0
	elif x <= 1+A[n-1]:
		return func(n-1,x-1)
	elif x == 2+A[n-1]:
		return P[n-1]+1
	elif x <= 2+2*A[n-1]:
		return P[n-1]+1+func(n-1,x-2-A[n-1])
	else:
		return 2*P[n-1]+1

print(func(n,x))

Submission status: Wrong Answer

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)
# print(A,P)

def func(n,x):
	if x == 1:
		return 0
	elif x <= 1+A[n-1]:
		return func(n-1,x-1)
	elif x == 2+A[n-1]:
		return P[n-1]+1
	elif x <= 2+2*A[n-1]:
		return P[n-1]+1+func(n-1,x-2-A[n-1])
	else:
		return 2*P[n-1]+1

print(func(n,x))

Submission status: Wrong Answer

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)
# print(A,P)

def func(n,x):
	if x == 1:
		return 0
	elif x <= 1+A[n-1]:
		return func(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+func(n-1,x-2-A[n-1])
	elif x == 3+2*A[n-1]:
		return 2*P[n-1]+1

print(func(n,x))

Submission status: Wrong Answer

Solution code:
def calc(n,x):
    global LData
    global PData

    if n == 0:
        if x == 1:
            ans = 1
        else:
            ans = 0

    else:
        if x*2-1 < LData[n]:
            ans = calc(n-1,x-1)
        elif x*2-1 == LData[n]:
            ans = PData[n-1]+1
        else:
            ans = PData[n-1]+1
            ans += calc(n-1,x-LData[n-1]-2)
    return ans

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

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

Submission status: Wrong Answer

Solution code:
def calc(n,x):
    global LData
    global PData

    if n == 0:
        if x == 1:
            ans = 1
        else:
            ans = 0

    else:
        if x*2-1 < LData[n]:
            ans = calc(n-1,x-1)
        elif x*2-1 == LData[n]:
            ans = PData[n-1]+1
        else:
            ans = PData[n-1]+1
            if x-LData[n-1]-2 >= 1:
                ans += calc(n-1,x-LData[n-1]-2)
    return ans

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

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

Submission status: Wrong Answer

Solution code:
def calc(n,x):
    global LData
    global PData

    if n == 0:
        return 1

    if x*2-1 < LData[n]:
        if x == 1:
            ans = 0
        else:
            ans = calc(n-1,x-1)
    elif x*2-1 == LData[n]:
        ans = PData[n-1]+1
    else:
        ans = PData[n-1]+1
        if x -LData[n-1]-2 > 1:
            ans += calc(n-1, x-LData[n-1]-2)
    return ans

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

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

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
count = 0
 
def count_patty(N, X, count):
    if N == 0:
        return 1 + count
    elif X == 1:
        return 0 + count
    elif X == 2**(N+1) - 1:
        return 2**N + count
    elif X == 2**(N+2) - 3:
        return 2**(N+1) - 1
    elif 1 < X < 2**(N+1) - 1:
        X -= 1
        N -= 1
        return count_patty(N, X, count)
    elif 2**(N+1) - 1 < X < 2**(N+2) - 3:
        count += 2**N
        X -= 2**(N+1) - 1
        N -= 1
        return count_patty(N, X, count)
 
print(count_patty(N, X, count))

Submission status: Wrong Answer

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

def count_patty(N, X, count):
    if N == 0:
        return 1
    elif X == 1:
        return 0
    elif X == 2**(N+1) - 1:
        return 2**N
    elif X == 2**(N+2) - 3:
        return 2**(N+1) - 1
    elif 1 < X < 2**(N+1) - 1:
        X -= 1
        N -= 1
        return count_patty(N, X, count)
    elif 2**(N+1) - 1 < X < 2**(N+2) - 3:
        count += 2**N
        X -= 2**(N+1) - 1
        N -= 1
        return count + count_patty(N, X, count)

print(count_patty(N, X, count))

Submission status: Wrong Answer

Solution code:
import sys
n, x = [int(i) for i in sys.stdin.readline().split()]
cur = 1
p = 1
ls = [cur]
p_ls = [p]
for i in range(50):
    cur = cur * 2 + 3
    p = p * 2 + 1
    ls.append(cur)
    p_ls.append(p)

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

Submission status: Wrong Answer

Solution code:
import sys
n, x = [int(i) for i in sys.stdin.readline().split()]
cur = 1
ls = [cur]
for i in range(50):
    cur = cur * 2 + 3
    ls.append(cur)

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