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:
def m(n): # n次元バーガーの層数
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a = a * 2 + 3
        return a

def paty(n): # n次元バーガーのパティの数
    a = 1
    if n >= 1:
        for i in range(n):
            a = a * 2 + 1
    return a

def a(n, x): #これが答えを返す
    x = x - 1
    if x == m(n-1) + 1:
        return paty(n-1) + 1
    elif x == 0:
        return 0
    elif x > m(n-1) + 1:
        return paty(n-1) + 1 + a(n-1, x - m(n-1) - 1)
    else:
        n = n - 1
        return a(n, x)

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

Submission status: Wrong Answer

Solution code:
def m(n): # n次元バーガーの層数
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a = a * 2 + 3
        return a

def paty(n): # n次元バーガーのパティの数
    a = 1
    if n >= 1:
        for i in range(n):
            a = a * 2 + 1
    return a

def a(n, x): #これが答えを返す
    x = x - 1
    if x == m(n-1) + 1:
        return paty(n-1) + 1
    elif x == 0:
        return 0
    elif x > m(n-1) + 1:
        return paty(n-1) + 1 + a(n-1, x - m(n-1) - 1)
    else:
        
        return a(n - 1, x)

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

Submission status: Wrong Answer

Solution code:
def m(n): # n次元バーガーの層数
    if n == 0:
        return 1
    else:
        a = 1
        for i in range(n):
            a = a * 2 + 3
        return a

def paty(n): # n次元バーガーのパティの数
    a = 1
    if n >= 1:
        for i in range(n):
            a = a * 2 + 1
    return a

def a(n, x): #これが答えを返す
    x = x - 1
    if x == m(n-1) + 1:
        return paty(n-1) + 1
    elif x == 0 and n == 0:
        return 1
    elif x == 0:
        return 0
    elif x > m(n-1) + 1:
        return paty(n-1) + 1 + a(n-1, x - m(n-1) - 1)
    else:
        n = n - 1
        return a(n, x)

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

Submission status: Wrong Answer

Solution code:
a = [1]
p = [1]
N,X = map(int,input().split())
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 0
    elif x <= a[n-1]+1:
        return f(n-1,x-1)
    else:
        return f(n-1,x-2-a[n-1])+p[n-1]+1
print(f(N,X))

Submission status: Wrong Answer

Solution code:
a = [1]
p = [1]
N,X = map(int,input().split())
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 0
    elif x <= a[n-1]+1:
        return f(n-1,x-1)
    elif x == a[n-1]+2:
        return p[n-1]+1
    elif x < 2*a[n-1]+2:
        return f(n-1,x-2-a[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 = [1]
b = [1]
for i in range(50):
  a += [2*a[-1]+3]
  b += [2*b[-1]+1]
  
def ans(N, X):
  if N == 0 : return X
  if X == 1 : return 1
  if X == a[N]: return b[N]
  if X == (a[N]+1)//2 : return 1 + b[N-1]
  if X < (a[N]+1)//2:
    return ans(N-1, X-1)
  else:
    return 1+b[N-1] + ans(N-1, X-(a[N]+1)//2)

print(ans(N,X))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
a = [1]
b = [1]
for i in range(50):
  a += [2*a[-1]+3]
  b += [2*b[-1]+1]
  
def ans(N, X):
  if N == 0 : return X
  if X == 1 : return 0
  if X == a[N]: return b[N]
  if X == (a[N]+1)//2 : return 1 + b[N-1]
  if X < (a[N]+1)//2:
    return ans(N-1, X-1)
  else:
    return 1+b[N-1] + ans(N-1, X-1-(a[N]+1)//2)

print(ans(N,X))

Submission status: Wrong Answer

Solution code:
N, X = map(int, input().split())
a = [1]
b = [1]
for i in range(50):
  a += [2*a[-1]+3]
  b += [2*b[-1]+1]
  
def ans(N, X):
  if N == 0 : return X
  if X == 1 : return 1
  if X == a[N]: return b[N]
  if X == (a[N]+1)//2 : return 1 + b[N-1]
  if X < (a[N]+1)//2:
    return ans(N-1, X-1)
  else:
    return 1+b[N-1] + ans(N-1, X-1-(a[N]+1)//2)

print(ans(N,X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


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

    # レベルL-1バーガー
    elif x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 2つ目のレベルL-1バーガーにかかる
    else:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)


print(solve(N, X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


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

    # レベルL-1バーガー
    elif x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 2つ目のレベルL-1バーガーにかかる
    else:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)


print(solve(N, X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン
        return 0

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x <= 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        return patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x <= 2 * thick[n - 1] + 2:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    elif x == 2 * thick[n - 1] + 3:
        return 2 * patti[n - 1] + 1


print(solve(N, X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン
        return 0

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x < 1 + thick[n - 1] + 1:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        return patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x < 2 * thick[n - 1] + 3:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    else:
        return 2 * patti[n - 1] + 1


print(solve(N, X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)


def solve(n, x):
    if x == 1:  # 一番下のバン
        return 0

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x < 1 + thick[n - 1]:
        return solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        return patti[n - 1] + 1

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x < 2 * thick[n - 1] + 3:
        return patti[n - 1] + 1 + solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    else:
        return 2 * patti[n - 1] + 1


print(solve(N, X))

Submission status: Wrong Answer

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

# レベルLバーガーの厚さ, レベルLバーガーに含まれるパティの数
thick, patti = [1], [1]
for i in range(N):
    thick.append(2 * thick[-1] + 3)
    patti.append(2 * patti[-1] + 1)

# グローバル変数
ans = 0


def solve(n, x):
    global ans
    if x == 1:  # 一番下のバン
        return

    # 一番下のバン + レベルL-1バーガーの途中まで
    elif 1 < x < 1 + thick[n - 1]:
        solve(n - 1, x - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ
    elif x == 2 + thick[n - 1]:
        ans += patti[n - 1] + 1
        return

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガーの途中まで
    elif 2 + thick[n - 1] < x < 2 * thick[n - 1] + 3:
        ans += patti[n - 1] + 1
        solve(n - 1, x - 1 - thick[n - 1] - 1)

    # 一番下のバン + レベルL-1バーガー + 真ん中のパティ + レベルL-1バーガー + 最後のバン
    else:
        ans += 2 * patti[n - 1] + 1
        return


solve(N, X)
print(ans)

Submission status: Wrong Answer

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

def n_total(N):
  total = 2**(N + 2) - 3
  return(total)

def p_total(N):
  total = 2**(N + 1) - 1
  return(total)

n = N
x = X
ans = 0
for i in range(N - 1):
  half = n_total(n - 1) + 2
  if x == half:
    ans += p_total(n - 1) + 1
    break
  elif x > half:
    ans += p_total(n - 1) + 1
    x -= n_total(n - 1) + 2
  else:
    x -= 1
  n -= 1
else:
  if x == 5:
    ans += 3
  else:
    ans += x - 1
print(ans)

Submission status: Wrong Answer

Solution code:
g_memo = {}
h_memo = {}
dp = {}

def g(l):
    if l < 0:
        return 0
    if l == 0:
        return 1
    if not l in g_memo:
        g_memo[l] = 3 + 2*g(l-1)
    return g_memo[l]

def h(l):
    if l < 0:
        return 0
    if l == 0:
        return 1
    if not l in h_memo:
        h_memo[l] = 1 + 2*h(l-1)
    return h_memo[l]

def solve(l, x):
    if x <= 0:
        return 0
    if l < 0:
        return 0
    if l == 0:
        return 1
    if x >= g(l):
        return h(l)
    if (l, x) in dp:
        return dp[l,x]
    y = 0
    res = 0
    # B
    y += 1
    # f(l-1)
    res += solve(l-1, x-y)
    y += g(l-1)
    # P
    if y <= x: # P
        res += 1
    y += 1
    # f(l-1)
    res += solve(l-1, x-y)
    y += g(l-1)
    # B 
    y += 1

    dp[l,x] = res
    return res

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

Submission status: Wrong Answer

Solution code:
def solve(N, X):
    thickness = [1]
    pate = [1]
    for L in range(1, N + 1):
        thickness.append(thickness[-1] * 2 + 3)
        pate.append(pate[-1] * 2 + 1)

    t = N
    P = 0
    X -= 1 # last index.
    while t >= 0:
        if t == 0:
            if 0 <= X:
                P += 1
            return P
        else:
            middle = (thickness[t] - 1) // 2
            if middle <= X:
                # top or middle
                X -= middle + 1
                P += pate[t - 1] + 1
                if middle == X:
                    return P
            else:
                # bottom
                X -= 1
            t -= 1
    return P

def test():
    def f(N, X, expect):
        print('N={}, X={}, expect={}'.format(N, X, expect))
        print(solve(N, X), expect)
    f(2, 7, 4)
    f(2, 8, 4)
    f(2, 9, 5)
    f(50, 4321098765432109, 2160549382716056)


if __name__ == '__main__':
    N, X = map(int, input().split())
    print(solve(N, X))

Submission status: Wrong Answer

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

a = [2**(n+2)-3 for n in range(51)]
b = [2**(n+1)-1 for n in range(51)]

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

print(func(N, X))

Submission status: Wrong Answer

Solution code:
n,k = map(int,input().split())
def burger(n):
  if n == 0:
    return 'P'
  else:
    return 'B' + burger(n-1) + 'P' + burger(n-1) + 'B'
a = list(burger(n))
b = a[::-1]
c = b[0:k-1]
count = 0
for i in c:
    if i == 'P':
        count += 1
print(a)
print(b)
print(c)
print(count)

Submission status: Wrong Answer

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


def pi(n):
    return 2**(n+1)-1


def ai(n):
    return 2**(n+2) - 3


def f(n, x):
    if x <= 1:
        return 0
    elif (1 < x) and (x <= 1 + ai(n-1)):
        return f(n - 1, x - 1)
    elif x == 2 + ai(n - 1):
        return pi(n - 1) + 1
    elif (2 + ai(n - 1) < x) and (x <= 2 + 2 * ai(n - 1)):
        return pi(n-1) + 1 + f(n-1, x-2-ai(n-1))
    elif x == ai(n):
        return pi(n)


print(f(n, x))

Submission status: Wrong Answer

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


def pi(n):
    return 2**(n+1)-1


def ai(n):
    return 2**(n+2) - 3


def f(n, x):
    if x == 1:
        return 0
    elif (1 < x) and (x <= 1 + ai(n-1)):
        return f(n - 1, x - 1)
    elif x == 2 + ai(n - 1):
        return pi(n - 1) + 1
    elif (2 + ai(n - 1) < x) and (x <= 2 + 2 * ai(n - 1)):
        return pi(n-1) + 1 + f(n-1, x-2-ai(n-1))
    elif x == ai(n):
        return pi(n)


print(f(n, x))

Submission status: Wrong Answer

Solution code:
Pat=[1]
for p in range(51):
    Pat.append(Pat[p]*2+1)
    
All=[1]
for a in range(51):
    All.append(All[a]*2+3)
    
N,X=map(int,input().split())
    
def saiki(n,x):
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<n:
        return 0
    elif x<(All[n]+1)//2-1:
        return saiki(n-1,x-1)
    elif x==(All[n-1]+2):
        return Pat[n-1]+1
    elif x<All[n]:
        return Pat[n-1]+1+saiki(n-1,x-2-All[n-1])
    else:
        return Pat[n]
print(saiki(N,X))

Submission status: Wrong Answer

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

def len_L(num):
    l = 0
    for i in range(num+1):
        if i== 0:
            l = 1
        else:
            l = 3 + 2*l
    return l

def count_P(level):
    P = 0
    for i in range(level+1):
        if i == 0:
            P = 1
        else:
            P = 2*P + 1
    return P

count = 0
if N == 1:
    count = min(X-1, 3)
else:
    while True:
        half = int((len_L(N) + 1) / 2)
        if X == 1:
            count += 0
            break
        elif X == N:
            count += count_P(N)
            break
        elif X == half:
            count += int((count_P(N) + 1) / 2)
            break
        elif X > half:
            count += int((count_P(N) + 1) / 2)
            X = X - half
            N = N - 1
            if N == 1:
                count += min(X-1, 3)
                break
        else:
            X = X - 1
            N = N - 1
            if N == 1:
                count += min(X-1, 3)
                break
print(count)

Submission status: Wrong Answer

Solution code:
n, x = map(int, input().split())
ans = 0
for i in range(n):
    if x > 2 ** (n + 1 - i) - 1:
        x -= 2 ** (n + 1 - i) - 1
        ans += 2 ** (n - i)
    elif x == 2 ** (n + 1 - i) - 1:
        ans += 2 ** (n - i)
        break
    elif x == 2 ** (n + 1 - i) - 2:
        ans += 2 ** (n - i) - 1
        break
    else:
        x -= 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,X = map(int, input().split())
def len_L(num):
    l = 0
    for i in range(num+1):
        if i== 0:
            l = 1
        else:
            l = 3 + 2*l
    return l

def get_level(n, x):
    for i in range(n+1):
        if x <= len_L(i):
            return(i)
            break

def count_P(level):
    P = 0
    for i in range(level+1):
        if i == 0:
            P = 1
        else:
            P = 2*P + 1
    return P

count = 0
if X == 1:
    count = 0
else:
    while X > 0:
        l = get_level(N,X)
        count += count_P(l-1)
        X = X - len_L(l-1) - 1
        if X == 0:
            break
        else:
            count += 1
            X = X - 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
allEatCache = {}
lenBurgerCache = {}


def nOfPatty(level, eat):
    if level == 0:
        return 1
    else:
        if level in allEatCache and eat >= lenBurger(level):
            return allEatCache[level]
        else:
            lenOfLowerLevel = lenBurger(level - 1)
            if eat <= 1:
                return 0
            if 2 <= eat <= 1 + lenOfLowerLevel:
                return nOfPatty(level - 1, eat - 1)
            if eat == 1 + lenOfLowerLevel + 1:
                return nOfPatty(level - 1, eat - 1) + 1
            else:
                tmp = nOfPatty(level - 1, eat - 1) + 1
                tmp += nOfPatty(level - 1, eat - 1 - lenOfLowerLevel - 1)
                allEatCache[level] = tmp
                return tmp


def lenBurger(level):
    if level == 0:
        return 1
    else:
        if level in lenBurgerCache:
            return lenBurgerCache[level]
        else:
            return 3 + lenBurger(level - 1) * 2


print(nOfPatty(50, 4321098765432109))

Submission status: Wrong Answer

Solution code:
def AP(N):
    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)

    return A,P

def count(N, X, A, P):

    if N == 0:
        return 1

    else: # N > 1
        if X == 1:
            return 0

        elif X <= 1 + A[N-1]:
            return count(N-1, X-1, A, P)

        elif X == 2 + A[N-1]:
            return P[N-1] + 1

        elif X <= 2+2*A[N-1]:
            return P[N-1] + 1 + count(N-1, X-2-A[N-1], A, P)

        else:
            print(X,3+2*A[N-1])
            return 2*P[N-1]+1


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

A, P = AP(N)

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

Submission status: Wrong Answer

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

def f(n, x):
  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 f(n -1, x - 2**(n + 1) + 1) + 2**n
  else:
     return 2**(n + 1) - 1

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

Submission status: Wrong Answer

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

N, X = map(int, input().split())
a = [1 for i in range(N + 1)]
p = [1 for i in range(N + 1)]
a[0] = 1;
p[0] = 1;

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

Submission status: Wrong Answer

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

thickness=[1]*(N+1)
Npatty=[1]*(N+1)

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

#print(thickness,Npatty)  
def countpatty(N,K):
  if K==1:
    return 0
  if 2<=K<=thickness[N-1]+1:
    return countpatty(N-1,K-1)
  if K==thickness[N-1]+2:
    return Npatty[N-1]+1
  if thickness[N-1]+3<=K<=thickness[N]-1:
    return Npatty[N-1]+1+countpatty(N-1,K-2-thickness[N-1])
  if K==thickness[N]:
    return 2*Npatty[N-1]+1

print(countpatty(N,K))

Submission status: Wrong Answer

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

thickness=[1]*(N+1)
Npatty=[1]*(N+1)

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

#print(thickness,Npatty)  
def countpatty(N,K):
  if K==1:
    count=0
  if 2<=K<=thickness[N-1]+1:
    count=countpatty(N-1,K-1)
  if K==thickness[N-1]+2:
    count=Npatty[N-1]+1
  if thickness[N-1]+3<=K<=thickness[N]-1:
    count=Npatty[N-1]+1+countpatty(N-1,K-2-thickness[N-1])
  if K==thickness[N]:
    count=2*Npatty[N-1]+1
  return count

print(countpatty(N,K))

Submission status: Wrong Answer

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

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


def dfs(n,x):
    if x >= (num[n]-1):
        return p[n]

    if x >= (num[n-1]) + 2:
        return p[n-1] + 1 + dfs(n-1,x-((num[n-1]) + 2))

    if x == (num[n-1]) + 1:
        return p[n-1]

    if x >= 2:
        return dfs(n-1,x-1)

    return 0

print(dfs(N,X))

Submission status: Wrong Answer

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

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

t = [0, 1, 2, 3, 3]

dp = {}

def solve(N, X):
    if dp.get((N, X), -1) != -1:
        return dp[(N,X)]
    elif N == 0:
        return 1
    elif N == 1:
        if X > 5:
            dp[(N, X)] = t[4] 
            return t[4]
        else:
            dp[ (N, X)] = t[X-1]
            return t[X-1]
    elif X <= b_len[N-1] + 1:
        dp[ (N, X) ] = solve(N-1, X-1)
        return solve(N-1, X-1)
    elif X == b_len[N-1] + 2:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1

        return solve(N-1, b_len[N-1]) + 1
    else:
        dp[ (N, X) ] = solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)
        return solve(N-1, b_len[N-1]) + 1 + solve(N-1, X-b_len[N-1]-2)

print (solve(N, X))

Submission status: Wrong Answer

Solution code:
#!/usr/env/python3
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: Wrong Answer

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

"""
解説参考
・必要な値を出してから再帰で場合分け
"""

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

# まず、それぞれのレベルについて全体の厚さとパティの枚数を求める
A = [1] * (N+1)
P = [1] * (N+1)
for i in range(1, N+1):
    A[i] = A[i-1] * 2 + 3
    P[i] = P[i-1] * 2 + 1

# レベルn、食べる厚さx
def dfs(n, x):
    # レベル0まで来て食べる厚さが残ってればパティ1枚
    if n == 0:
        if x >= 0:
            return 1
        else:
            return 0
    # ひとつ前の総数 + 左端バンズ = 真ん中のパティの手前まで
    if x <= A[n-1] + 1:
        # 前のレベルを調べる(食べる厚さは左端バンズを引く)
        return dfs(n-1, x-1)
    # 食べる厚さが真ん中のパティまでより多い
    else:
        # ひとつ前の総取り + 真ん中 + 前のレベルを調べる
        # (食べる厚さは前半のひとつ前の分と、左端バンズと真ん中パティを引く)
        # ※右端バンズを食べる場合でも、最終的にn == 0で1を返す時xの残数が1多いだけなので考慮しなくていい
        return P[n-1] + 1 + dfs(n-1, x-A[n-1]-2)

print(dfs(N, X))

Submission status: Wrong Answer

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

"""
解説参考
・必要な値を出してから再帰で場合分け
"""

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

# まず、それぞれのレベルについて全体の厚さとパティの枚数を求める
A = [1] * (N+1)
P = [1] * (N+1)
for i in range(1, N+1):
    A[i] = A[i-1] * 2 + 3
    P[i] = P[i-1] * 2 + 1

# レベルn、食べる厚さx
def dfs(n, x):
    # レベル0まで来たら無条件でパティ1枚
    if n == 0:
        return 1
    # 食べる厚さ1枚だとバンズだけでパティなし
    if x <= 1:
        return 0
    # ひとつ前の総数 + 左端バンズ = 真ん中のパティの手前まで
    elif 1 < x <= A[n-1] + 1:
        # 前のレベルを調べる(食べる厚さは左端バンズを引く)
        return dfs(n-1, x-1)
    # 食べる厚さが真ん中のパティまでより多い
    else:
        # ひとつ前の総取り + 真ん中 + 前のレベルを調べる
        # (食べる厚さは前半のひとつ前の分と、左端バンズと真ん中パティを引く)
        # ※右端バンズを食べる場合でも、最終的にn == 0で1を返す時xの残数が関係ないので考慮しなくていい
        return P[n-1] + 1 + dfs(n-1, x-A[n-1]-2)

print(dfs(N, X))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
 
def burg(l):
    if l ==0:
        return "P"
    else:
        return "B"+burg(l-1)+"p"+burg(l-1)+"B"

n, x = map(int, input().split())
print(burg(n))
eaten = burg(n)[0:x]
print(eaten.count("P"))

Submission status: Wrong Answer

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

N = int(N)
X = int(X)

all = 2**(N+2)-3
b_all = 0
for i in range(N+1):
    if i > 0:
        b_all += 2**i

p_all = all - b_all

first = 1
last = all

get = 0
for i in range(N):
    if i < N-1:
        if (first + last) / 2 == X:
            get += (p_all + 1) / 2
            break

        elif (first + last) / 2 < X:
            get += (p_all + 1) / 2
            p_all -= (p_all + 1) / 2
            first = (first + last) / 2 + 1
            last = last - 1

            if first == X:
                break
        elif (first + last) / 2 > X:
            p_all = (p_all - 1) / 2
            last = (first + last) / 2 - 1
            first = first + 1

            if last == X:
                get += p_all
                break
    else:
        if first == X:
            break
        elif last == X:
            get += 3
        else:
            get += X - first
            break

print(int(get))

Submission status: Wrong Answer

Solution code:
def cal(N, i):
    if N > 0:
        return 2 * cal(N - 1, i) + i
    elif N == 0:
        return 1
    else:
        return 0

def pCal(N ,X):
    half = cal(N, 3) // 2
    pTmp = cal(N - 1, 1)
    if X == 1 and N == 0:
        return 1
    elif X <= N:
        return 0
    elif X == half:
        return pTmp
    elif X == half + 1:
        return pTmp + 1
    elif X < half:
        return pCal(N - 1, X - 1)
    elif X > half + 1:
        return (pTmp + 1) + pCal(N - 1, X - (half + 1))

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

Submission status: Wrong Answer

Solution code:
def cal(N, i):
    if N > 0:
        return 2 * cal(N - 1, i) + i
    else:
        return 1

def pCal(N ,X):
    half = cal(N, 3) // 2
    pTmp = cal(N - 1, 1)
    if X <= N:
        return 0
    elif X == half:
        return pTmp
    elif X == half + 1:
        return pTmp + 1
    elif X < half:
        return pCal(N - 1, X - 1)
    elif X > half + 1:
        return (pTmp + 1) + pCal(N - 1, X - (half + 1))

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

Submission status: Wrong Answer

Solution code:
def cal(N, i):
    if N > 0:
        N -= 1
        return 2 * cal(N, i) + i
    else:
        return 1

def pCal(N ,X):
    half = cal(N, 3) // 2
    pTmp = cal(N - 1, 1)
    if X < N:
        return 0
    elif X == half:
        return pTmp
    elif X == half + 1:
        return pTmp + 1
    elif X < half:
        return pCal(N - 1, X - 1)
    elif X > half + 1:
        return (pTmp + 1) + pCal(N - 1, X - (half + 1))

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

Submission status: Wrong Answer

Solution code:
def cal(N, i):
    if N > 0:
        N -= 1
        return 2 * cal(N, i) + i
    else:
        return 1

def pCal(N ,X):
    half = cal(N, 3) // 2
    pTmp = cal(N - 1, 1)
    if X == 0:
        return 0
    elif X > half + 1:
        return (pTmp + 1) + pCal(N - 1, X - (half + 1))
    elif X < half:
        return pCal(N - 1, X - 1)
    elif X == half:
        return pTmp
    elif X == half + 1:
        return pTmp + 1

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

Submission status: Wrong Answer

Solution code:
n,x=[int(i)  for i in input().split()]
a=[1]
p=[1]
for i in range(n):
    a.append(a[i]*2+3)
    p.append(p[i]*2+1)
def f(n,x):
    if x==1:
        return 0
    elif 1<x<=1+a[n-1]:
        return f(n-1,x-1)
    elif x==a[n-1]+2:
        return p[n-1]+1
    elif 2+a[n-1]<x<=2*a[n-1]+2:
        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:
def height(level):
    hei = 1
    for i in range(level):
        hei = 3 + 2 * hei
    return hei

def patty(level):
    pat = 1
    for i in range(level):
        pat = 1 + 2 * pat
    return pat

def ans(level, under):
    if under <= 1:
        return 0
    elif under <= 1 + height(level - 1):
        return ans(level - 1, under - 1)
    elif under == 2 + height(level - 1):
        return 1 + patty(level - 1)
    elif under <= 2 + 2 * height(level - 1):
        return 1 + patty(level - 1) + ans(level - 1, under - 2 - height(level - 1))
    else:
        return 1 + 2 * patty(level - 1)
    
n, x = map(int, input().split())
print(ans(n, x))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

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

def func(lv, id):
    sz = 4 * 2 ** lv - 3
    num = 2 * 2 ** lv - 1
    mid = (sz + 1) / 2
    if lv == 0:
        return 1
    if id == 1:
        return 0
    if id == mid:
        return (num - 1) / 2 + 1
    if id == sz:
        return num
    if 1 < id < mid:
        return func(lv - 1, id - 1)
    if mid < id < sz:
        return func(lv - 1, id - (sz - 3) / 2 - 2) + (num - 1) / 2

print func(N, X)

Submission status: Wrong Answer

Solution code:
n,x=[int(i) for i in input().split()]
p=[1]
b=[0]
z=[]
for i in range(n):
  p.append(p[i]*2+1)
  b.append(b[i]*2+2)
  z.append(p[i]+b[i])
ans=0
ici=1
for i in range(n-1, -1, -1):
  if x-ici>z[i]+1:
    ici+=z[i]+2
    ans+=p[i]+1
  elif x-ici<z[i]:
    ici+=1
  else:
    ans= ans+p[i]+1 if x-ici==z[i]+1 else ans+p[i]
    break
print(ans)

Submission status: Wrong Answer

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 1
    elif X == 0:
        return 0
    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:
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
    elif X == 0:
        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: Wrong Answer

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 1
    elif X == 0:
        return 0
    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:
n,x=[int(i) for i in input().split()]
p=[1]
b=[0]
z=[]
for i in range(n):
  p.append(p[i]*2+1)
  b.append(b[i]*2+2)
  z.append(p[i]+b[i])
ans=0
ici=1
for i in range(n-1, -1, -1):
  if x-ici>z[i]+1:
    ici+=z[i]+2
    ans+=p[i]+1
  elif x-ici<z[i]+1:
    ici+=1
  else:
    ans+=p[i]+1
    break
print(ans)