Problem:


Score : 400 points

Problem Statement

In some other world, today is Christmas.

Mr. Takaha decides to make a multi-dimensional burger in his party. A level-L burger (L is an integer greater than or equal to 0) is the following thing:

A level-0 burger is a patty.

A level-L burger (L \geq 1) is a bun, a level-(L-1) burger, a patty, another level-(L-1) burger and another bun, stacked vertically in this order from the bottom.

For example, a level-1 burger and a level-2 burger look like BPPPB and BBPPPBPBPPPBB (rotated 90 degrees), where B and P stands for a bun and a patty.

The burger Mr. Takaha will make is a level-N burger. Lunlun the Dachshund will eat X layers from the bottom of this burger (a layer is a patty or a bun). How many patties will she eat?

Constraints

1 \leq N \leq 50

1 \leq X \leq ( the total number of layers in a level-N burger )

N and X are integers.

Input

Input is given from Standard Input in the following format:

N X

Output

Print the number of patties in the bottom-most X layers from the bottom of a level-N burger.

Sample Input 1

2 7

Sample Output 1

4

There are 4 patties in the bottom-most 7 layers of a level-2 burger (BBPPPBPBPPPBB).

Sample Input 2

1 1

Sample Output 2

0

The bottom-most layer of a level-1 burger is a bun.

Sample Input 3

50 4321098765432109

Sample Output 3

2160549382716056

A level-50 burger is rather thick, to the extent that the number of its layers does not fit into a 32-bit integer.



Sample input:
2 7


Sample output:
4

Submission status: Accepted

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

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

print(dp(N,X))

Submission status: Accepted

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

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

def f(n, x):
    if n == 0:
        if x <= 0:
            return 0
        else:
            return 1
    elif x <= a[n - 1] + 1:
        return f(n - 1, 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())
def patty(L):
# レベルLバーガーにパティがいくらあるか
    p = 1
    for i in range(L):
        p = 2 * p + 1
    return (p)
def vol(L):
# レベルLバーガーが何層か
    m = 1
    for i in range(L):
        m  = m * 2 + 3
    return (m)
def eated(L, X):
# レベルLバーガーを下からX層に何枚パティがあるか
    if L == 0:
        return 1
    m = vol(L)
    if X == 1 or X == 0:
        #print("下から１枚")
        return 0
    elif X == (m + 1) / 2:
        #print("ちょうど真ん中")
        #print(str(L-1) + "バーガーのパティ＋１枚")
        return patty(L-1) + 1
    elif X < (m + 1) / 2:
        #print("下半分")
        #print(str(L-1) + "バーガーを考える")
        return eated(L-1, X-1)
    else:
        #print("上半分")
        #print(str(L) + "バーガーのパティを上から" + str(X) + "枚食べたと考える")
        return patty(L) - eated(L, m - X)
print(eated(n, x))

Submission status: Accepted

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

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)

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

Submission status: Accepted

Solution code:
memo = [[0, 1]]

def f(n, b, p, k):
	if b+p == k: return [b, p]
	if n == 0: return [b, p+1]
	newlst1 = [b+1, p]
	if newlst1[0]+newlst1[1] == k: return newlst1
	newlst2 = [newlst1[0]+memo[n-1][0], newlst1[1]+memo[n-1][1]]
	if newlst2[0] + newlst2[1] == k: return newlst2
	if newlst2[0] + newlst2[1] > k: return f(n-1, newlst1[0], newlst1[1], k)
	newlst3 = [newlst2[0], newlst2[1]+1]
	if newlst3[0]+newlst3[1] == k: return newlst3
	newlst4 = [newlst3[0]+memo[n-1][0], newlst3[1]+memo[n-1][1]]
	if newlst4[0]+newlst4[1] == k: return newlst4
	if newlst4[0]+newlst4[1] > k: return f(n-1, newlst3[0], newlst3[1], k)
	return [newlst4[0]+1, newlst4[1]]

N, K = map(int, input().split())
for i in range(1, N):
	memo.append([2*memo[i-1][0]+2, 2*memo[i-1][1]+1])
print(f(N, 0, 0, K)[1])

Submission status: Accepted

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

Submission status: Accepted

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

def dp(cur,X,ans):
    if cur==0:
        if X==0:
            return ans
        else:
            return ans+1
    elif X==0:
        return ans
    elif X>0 and X<=1+L[cur-1]:
        return dp(cur-1,X-1,ans)
    elif X==2+L[cur-1]:
        return ans+P[cur-1]+1
    elif X>2+L[cur-1] and X<L[cur]:
        return dp(cur-1,X-L[cur-1]-2,ans+P[cur-1]+1)
    else:
        return ans+P[cur]
        
print(dp(N,X,0))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
pty = [[] for i in range(n + 1)]
lay = [[] for i in range(n + 1)]
pty[0] = 1
lay[0] = 1
for L in range(1, n + 1):
    pty[L] = 2 * pty[L - 1] + 1
    lay[L] = 2 * lay[L - 1 ] + 3
ans = 0
while x > 0:
    if x >= lay[L] + 1:
        x -= lay[L] + 1
        ans += pty[L] + 1
    elif x == lay[L]:
        x -= lay[L]
        ans += pty[L]
    else:
        L -= 1
        x -= 1
print(ans)

Submission status: Accepted

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

def eat(level, X):
    if X == 0:
        return 0
    if level == 0:
        return X
    if (X-1) <= T_array[level-1]:
        return eat(level-1, X-1)
    else:
        return P_array[level-1] + 1 + eat(level-1, min(X-T_array[level-1]-2, T_array[level-1]))


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

P_array = [0] * 51
B_array = [0] * 51
T_array = [0] * 51
P_array[0] = 1
B_array[0] = 0
T_array[0] = 1

for i in range(1, 51):
    P_array[i] = P_array[i-1]*2 + 1
    B_array[i] = B_array[i-1]*2 + 2
    T_array[i] = P_array[i] + B_array[i]

print(eat(N,X))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Christmas
https://atcoder.jp/contests/abc115/tasks/abc115_d

"""
import sys


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


def solve(N, X):
    def eat_p(level, x):
        if level == 0:
            return 0 if x <= 0 else 1
        elif x <= 1 + T[level-1]:
            return eat_p(level-1, x-1)
        else:
            return P[level-1] + 1 + eat_p(level-1, x-2-T[level-1])

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

    return eat_p(N, X)


def main(args):
    N, X = map(int, input().split())
    ans = solve(N, X)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

def f(n, k):
    if k == 0:
        return 1 if n==1 else 0
    elif n == 1:
        return 0
    elif 1 < n <= 1 + a[k-1]:
        return f(n-1, k-1)
    elif n == 2 + a[k-1]:
        return 1 + p[k-1]
    elif 2 + a[k-1] < n <= 2 + 2 * a[k-1]:
        return 1 + p[k-1] + f(n-2-a[k-1], k-1)
    elif n == 3 + 2 * a[k-1]:
        return 1 + 2 * p[k-1]
    else:
        return 'Err'

ans=f(s, k)
print(ans)

Submission status: Accepted

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

print(ans(N,X))

Submission status: Accepted

Solution code:
N,X =  map(int, input().split())
a = [1 for i in range(N)]
p = [1 for i in range(N)]
for i in range(1,N):
    a[i] = a[i-1]*2 + 3
    p[i] = p[i-1]*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-a[N-1]-2)
print(f(N,X))

Submission status: Accepted

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

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


def calc(N, X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1 + L[N - 1]:
        return calc(N - 1, X - 1)
    else:
        return P[N - 1] + 1 + calc(N - 1, X - 2 - L[N - 1])


print(calc(N, X))

Submission status: Accepted

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


def solve_p(N, X):
    if X <= 0:
        return 0
    elif N == 0:
        return 1
    else:
        if X == (nums[N]+1) // 2:
            return (p_count[N]+1) // 2
        elif X < (nums[N]+1) // 2:
            return solve_p(N - 1, X - 1)
        else:
            #print("num", nums[N])
            return p_count[N-1]+1+solve_p(N-1, X-(nums[N]+1)//2)


print(solve_p(N, X))
"""
burger = ["P"]
for i in range(N):
    burger.append(("B"+burger[i]+"P"+burger[i]+"B"))
# print(burger)  # [N + 1])

# print(burger[N])

print(burger[N][:x].count("P"))
"""

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

Submission status: Accepted

Solution code:
def putty():
    N,X = map(int,input().split())
    ans = 0

    for i in range(0,N+1)[::-1]:
        width = 2**(i+2)-3
        if X <= i:   return ans
        elif X >= width - i:    return ans + 2**(i+1)-1
        else:
            mid = (width + 1) // 2
            if X == mid:    return ans + 2**(i)
            elif X < mid:   X -= 1 
            else:
                X -= 2**(i+1)-3 + 2 
                ans += 2**(i)

print(putty())

Submission status: Accepted

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

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

Submission status: Accepted

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

# パティの枚数
p = [1]
for i in range(n):
    p.append(p[i] * 2 + 1)

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

print(f(n, x))

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(N):
    b.append(b[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 <= b[N-1] + 1:
        return f(N-1, X-1)
    else:
        return p[N-1] + 1 + f(N-1, X-2-b[N-1])
    
print(f(N, X))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
a = [1]
p = [1] # レベル0バーガーは パティ1 枚
# レベル1バーガーは BPPPB
# レベル2バーガーは B,BPPPB,P,BPPPB,B  
for i in range(n):
  a.append(a[i]*2+3)
  p.append(p[i]*2+1)
  
def rec(n, x):
  if n==0:
    return 0 if x<=0 else 1
  elif x <= 1+a[n-1]:
    return rec(n-1, x-1)
  else:
    return p[n-1]+1+rec(n-1, x-2-a[n-1])
print(rec(n, x))

Submission status: Accepted

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

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

def rec(N, X):    

    if X <= 0:
        return(0)
        
    if N == 0:
        return(1)
    
    if X < L[N - 1] + 2:
        return(rec(N - 1, X - 1))
        
    if X == L[N - 1] + 2:
        return(P[N - 1] + 1)
    
    if X > L[N - 1] + 2:
        return(P[N - 1] + 1 + rec(N - 1, X - L[N - 1] - 2))


print(rec(N, X))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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 < (2 + a[N-1]):
            return _f(N-1, X-1)
        elif X == (2 + a[N-1]):
            return 1 + p[N-1]
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _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
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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)
        elif X == (2 + a[N-1]):
            return 1 + p[N-1]
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _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
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd



def solve(N: int, X: int):
    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)
        elif X < a[N]:
            return p[N-1] + 1 + _f(N-1, X - 2 - a[N-1])
        else:
            return p[N]

    return _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
    result = solve(N, X)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
p=lambda n:2**(n+1)-1
a=lambda n:2**(n+2)-3
def f(n,x):
    if n==0:
        return 0 if x<=0 else 1
    if x>1+a(n-1):
        return p(n-1)+1+f(n-1,x-2-a(n-1))
    return f(n-1,x-1)
n,x=map(int,input().split())
print(f(n,x))

Submission status: Accepted

Solution code:
p=lambda n:2**(n+1)-1
a=lambda n:2**(n+2)-3
def f(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 p(n-1)+1+f(n-1,x-2-a(n-1))
n,x=map(int,input().split())
print(f(n,x))

Submission status: Accepted

Solution code:
p = lambda n:2**(n+1)-1
a = lambda n:2**(n+2)-3


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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())


def rec(n: int, x: int, a: list, p: list) -> int:
    if x <= 0:
        raise ValueError

    elif n == 0:
        return 1

    elif x == 1:
        return 0

    elif 1 < x < a[n-1] + 2:
        return rec(n-1, x-1, a, p)

    elif x == a[n-1] + 2:
        return p[n-1] + 1

    elif a[n-1] + 2 < x < 2*a[n-1] + 3:
        return p[n-1] + 1 + rec(n-1, x - a[n-1] - 2, a, p)

    elif x == 2*a[n-1] + 3:
        return 2 * p[n-1] + 1

n,x = li()
a = [1]
p = [1]

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 16:57:17 2019

@author: Yamazaki Kenichi
"""

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

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

ans = 0
for i in range(2,N+2):
    if X - (dp[-i][1] + 2) >= 0:
        ans += dp[-i][0] + 1
        X -= (dp[-i][1] + 2)
#        print(ans,X,dp[-i])
    else:
        X -= 1
#        print(ans,X,dp[-i])
    if i == N+1 and X >= 1:
        ans += 1
#        print(ans,X,dp[-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 dfs(N, X):
  if N == 0:
    return 0 if X <= 0 else 1
  elif X <= a[N-1] + 1:
    return dfs(N-1, X-1)
  else:
    return p[N-1] + 1 + dfs(N-1, X-a[N-1]-2)
  
print(dfs(N, X))

Submission status: Accepted

Solution code:
# coding: utf-8

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)

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

print(f(n,x))

Submission status: Accepted

Solution code:
def bread_cnt(lev):
  return 2**(lev+1) - 2

def patty_cnt(lev):
  return 2**(lev+1) - 1

def burger_cnt(lev):
  return 2**(lev+2) - 3

def solve(n, x):
  return _solve(n, x, 0)
  
def _solve(n, x, p):
  total_s = burger_cnt(n)
  mid = (total_s+1)//2
  
  if x==1:
    return p + (1 if n==0 else 0)
  elif 1 < x and x <= mid:
    reach_mid = 1 if x==mid else 0
    return _solve(n-1, x-1-reach_mid, p+reach_mid)
  elif mid < x and x < total_s:
    return _solve(n-1, x-2-burger_cnt(n-1), p+1+patty_cnt(n-1))
  elif x == total_s:
    return p+patty_cnt(n)

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

Submission status: Accepted

Solution code:
N,K = map(int,input().split())
import sys
sys.setrecursionlimit(10000000)

a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)
def dfs(N,X):
    #print(N,X)
    if N == 0:
        return 0 if X != 1 else 1
    elif X <= 1 + a[N-1]:
        return dfs(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 + dfs(N-1, X-2-a[N-1])
    else:
        return 2*p[N-1]+1
    
print(dfs(N,K))

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 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:
memo = [-1]*100
mepp = [-1]*100
def getPB(N,k):
    if (N==0):
        return 1,1 if k>0 else 0
    if (memo[N] != -1 and k >= memo[N] and mepp[N]!=-1 ):
        return memo[N] , mepp[N]
    if (memo[N] != -1 and k <= 0):
        return memo[N] , 0
    #c =  1+getPB(N-1)+1+getPB(N-1)+1 # BxPxB
    c,p = 1,0
    _c,_p=getPB(N-1,k-c)
    c,p=c+_c,p+_p
    c,p=c+1,(p+1 if (k-c>0) else p)
    _c,_p=getPB(N-1,k-c)
    c,p=c+_c,p+_p
    c += 1
    memo[N] = c
    if (k-c>=0):
        mepp[N] = p
    return c,p
N,X = [ int(it) for it in input().split() ]
print ( getPB(N,X)[1] )

Submission status: Accepted

Solution code:
import sys
from math import *
from fractions import gcd
readints=lambda:map(int, input().strip('\n').split())

calc=[0]*55
calc[0]=1
for i in range(1,52):
    calc[i] = 3 + 2*calc[i-1]


n,x=readints()
x-=1 # 0-index


cache={}

def solve(L, i):
    if i<0:
        return 0
    if L==0:
        return 1
    else:
        if (L,i) in cache:
            return cache[(L,i)]
        m = calc[L] // 2
        res = 0
        if i>=m:
            res += solve(L-1,calc[L-1]-1) + 1
            res += solve(L-1,i-m-1)
            cache[(L,i)]=res
        else:
            cache[(L,i)]=solve(L-1, i-1)
        return cache[(L,i)]
        


print(solve(n,x))

Submission status: Accepted

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

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

ans = 0

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


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

Submission status: Accepted

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

burger = [[1,1]]

for i in range(n):
    burger.append([burger[-1][0]*2+3,burger[-1][1]*2+1])

# レベルn, 下からx段, 食べるパティp枚
def eat(n,x):
    if n==0:
        if x>0:
            return 1
        else:
            return 0
    if x < 1:
        return 0
    if 1 <= x <= 1+burger[n-1][0]:
        return eat(n-1,x-1)
    if x == 2 + burger[n-1][0]:
        return burger[n-1][1]+1
    if x>2+burger[n-1][0]:
        return eat(n-1,x-2-burger[n-1][0])+burger[n-1][1]+1


print(eat(n,x))

Submission status: Accepted

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

b = [[1,1]]

for i in range(n):
    b.append([b[-1][0]*2+3, b[-1][1]*2+1])

ans = 0
for i in range(len(b)):
    if x >= b[-1-i][0]:
        x -= b[-1-i][0]
        ans += b[-1-i][1]
        if x > 0:
            x-=1
            ans += 1
        if x>=b[-1-i][0]:
            x -= b[-1 - i][0]
            ans += b[-1 - i][1]
            break
    x-=1
    if x<=0:
        break

print(ans)

Submission status: Accepted

Solution code:

def count(N):
    pn = 2**(N+1)-1 #パテ
    bn = 2**(N+1)-2 #バン
    rn = pn + bn    #バーガー枚数(右端)
    return pn, bn, rn
    
if __name__ == "__main__":
    N, X = map(int, input().split())
    pn,bn,rn = count(N)
    mid = (1+rn)//2
    cnt = 0
    # Xの位置関係で場合分け
    while N > 0:
        # print(X,"l m r",1,mid,rn)
        # print("cnt",N,cnt)
        pn_prev, bn_prev, rn_prev = count(N-1)

        if X == 1:
            break
        elif X == mid:
            cnt +=  pn_prev + 1
            break
        elif rn == X:
            cnt += 2*pn_prev + 1
            break
        elif 1 < X < mid:
            X -= 1
        elif mid < X < rn:
            cnt += pn_prev + 1
            X -= mid

        pn, bn, rn = pn_prev,bn_prev,rn_prev
        mid = (1+rn)//2
        N -= 1
        if N == 0:
            cnt += 1
    print(cnt) #0段目のパテ

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 p_num(n,x):
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<= 1+a[n-1]: #このレベルのバーガーで終了するとき
        return p_num(n-1,x-1)
    else:
        return p[n-1] + 1 + p_num(n-1,x-2-a[n-1])
print(p_num(N,X))

Submission status: Accepted

Solution code:
N, X = [int(a) for a in input().split(" ")]
numt = [1]*51
nump = [0]*51
for i in range(1,51):
    numt[i]=2*numt[i-1]+3
    nump[i]=2*nump[i-1]+1

def rec(n, i):
    if n==0:
        return 1
    if i==0:
        return 0
    elif i==numt[n]-1:
        return 2*nump[n]+1
    mid = numt[n]//2
    if i==mid:
        return 1+nump[n]
    elif i>mid:
        return rec(n-1, i-mid-1)+nump[n]+1
    else:
        return rec(n-1, i-1)
    
print(rec(N, X-1))

Submission status: Accepted

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


def main(n, x):
    if n == 0:
        if x >= 0:
            return 1
        else:
            return 0
    if x == 0:
        return 0
    if x == 2 ** (n + 1) - 2:
        return 2 ** n
    if x < 2 ** (n + 1) - 2:
        return main(n - 1, x - 1)
    return 2 ** n + main(n - 1, x - (2 ** (n + 1) - 1))


print(main(n, x))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000)

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

ans = 0
for n in range(N,-1,-1):
  if X > (2**(n+2) - 3) / 2 :
    ans += 2**n #- 1 + 1
    X = X - (2**(n+1) - 3) - 2
  else:
    X -= 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 dfs(N,X):
    if N == 0:
        return 0 if X <= 0 else 1
    elif X <= 1+a[N-1]:
        return dfs(N-1,X-1)
    else:
        return p[N-1]+1+dfs(N-1,X-2-a[N-1])

print(dfs(N,X))

Submission status: Accepted

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

max_layer = 50
all_layer = [0]*(max_layer+1)
pate = [0]*(max_layer+1)
all_layer[0] = 1
pate[0] = 1

for i in range(1,max_layer+1):
    all_layer[i] = 2*all_layer[i-1] + 3
    pate[i] = 2*pate[i-1] + 1

def dfs(level, remain):
    ans = 0
    if level == 0:
        return 1

    if remain > 0:
        remain -= 1
    if remain > 0:
        if all_layer[level-1] <= remain:
            remain -= all_layer[level-1]
            ans += pate[level-1]
        else:
            ans += dfs(level-1, remain)
            return ans
    if remain > 0:
        remain -= 1
        ans += 1
    if remain > 0:
        if all_layer[level-1] <= remain:
            remain -= all_layer[level-1]
            ans += pate[level-1]
        else:
            ans += dfs(level-1, remain)
            return ans
    return ans
print(dfs(N, X))

Submission status: Accepted

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

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

Submission status: Accepted

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

# メモ化するための初期化
a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def f(N, X):
    # レベル0
    if N == 0:
        # 0層以下
        if X <= 0: # X <= 0 や X > a_N を許容し解説本文から簡略化
            return 0
        # 1層以上 (レベル0から実質1層のみ)
        else:
            return 1
    # レベル1以上
    # B ~ 以下
    elif X <= 1 + a[N - 1]:
        return f(N - 1, X - 1)
    # B ~ P ~ B 以下
    else:
        return p[N - 1] + 1 + f(N - 1, X - 2 - a[N - 1])

print(f(N, X))

Submission status: Accepted

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

# メモ化するための初期化
a, p = [1], [1]
for i in range(N):
    a.append(a[i] * 2 + 3)
    p.append(p[i] * 2 + 1)

def f(N, X):
    # X <= 0 や X > a_N を許容し解説本文から簡略化
    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:
N, X = map(int, input().split())


def f(n):
    # レベルnの総数
    if n == 0:
        return 1
    else:
        return 2 * f(n - 1) + 3


def g(n):
    # レベルnのpの数
    if n == 0:
        return 1
    else:
        return 2 * g(n - 1) + 1


def dfs(n, x):
    # 総数
    m = f(n)
    # 真ん中
    a = (m + 1) // 2

    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x < a:
        return dfs(n - 1, x - 1)
    elif x == a:
        return g(n - 1) + 1
    elif x >= a:
        return g(n - 1) + 1 + dfs(n - 1, x - a)
    elif x == m:
        return 2 * g(n - 1) + 1


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

Submission status: Accepted

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


P, H = [1], [1]
for i in range(50):
    P.append(P[-1] * 2 + 1)
    H.append(H[-1] * 2 + 3)


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

    elif 1 < x <= H[n - 1] + 1:
        return dfs(n - 1, x - 1)

    elif x == H[n - 1] + 2:
        return P[n - 1] + 1

    elif H[n - 1] + 2 < x <= 2 * H[n - 1] + 2:
        return P[n - 1] + 1 + dfs(n - 1, x - H[n - 1] - 2)

    elif x == 2 * H[n - 1] + 3:
        return 2 * P[n - 1] + 1


print(dfs(N, X))