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:
def f(v,i):s,n=4*2**v-3,2*2**v-1;m=s/2+1;return 0 if i<1 or i>s else[0,f(v-1,i-1),n/2+1,f(v-1,i-m)+n/2+1,n,1][(i>1)+(i>=m)+(i>m)+(i>=s)+(v==0)*3]
print f(*map(int,raw_input().split()))

Submission status: Accepted

Solution code:
def f(v,i):s,n=4*2**v-3,2*2**v-1;m=s/2+1;return 0 if i < 1 or i > s else [0, f(v - 1, i - 1), n / 2 + 1, f(v - 1, i - s / 2 - 1) + n / 2 + 1, n, 1][(i > 1) + (i >= m) + (i > m) + (i >= s) + (v == 0) * 3]

print f(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
def f(v, i):s, n = 4 * 2 ** v - 3, 2 * 2 ** v - 1;m = (s + 1) / 2;return 0 if i < 1 or i > s else [0, f(v - 1, i - 1), n / 2 + 1, f(v - 1, i - s / 2 - 1) + n / 2 + 1, n, 1][(i > 1) + (i >= m) + (i > m) + (i >= s) + (v == 0) * 3]

print f(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
def f(v, i):
    s = 4 * 2 ** v - 3
    n = 2 * 2 ** v - 1
    m = (s + 1) / 2
    return 0 if i < 1 or i > s else [0, f(v - 1, i - 1), n / 2 + 1, f(v - 1, i - s / 2 - 1) + n / 2 + 1, n, 1][(i > 1) + (i >= m) + (i > m) + (i >= s) + (v == 0) * 3]

print f(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
def f(v, i):
    s = 4 * 2 ** v - 3
    n = 2 * 2 ** v - 1
    m = (s + 1) / 2
    if i < 1 or i > s: return 0
    return [0, f(v - 1, i - 1), n / 2 + 1, f(v - 1, i - s / 2 - 1) + n / 2 + 1, n, 1][(i > 1) + (i >= m) + (i > m) + (i >= s) + (v == 0) * 3]

print f(*map(int, raw_input().split()))

Submission status: Accepted

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

print func(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
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 / 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 / 2 - 1) + num / 2 + 1

print func(*map(int, raw_input().split()))

Submission status: Accepted

Solution code:
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 + 1

print func(*map(int, raw_input().split()))

Submission status: Accepted

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

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 + 1

print func(*map(int, raw_input().split()))

Submission status: Accepted

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 + 1

print func(N, X)

Submission status: Accepted

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

def cnt_pat(x, n):
  if n == 0:
    return 1
  if x == 1:
    return 0
  if x <= mai[n] // 2:
    return cnt_pat(x-1, n-1)
  if x == mai[n] // 2 + 1:
    return pat[n-1] + 1
  if x < mai[n]:
    return pat[n-1] + 1 + cnt_pat(x-mai[n]//2-1, n-1)
  if x == mai[n]:
    return pat[n]
  
print(cnt_pat(X, N))

Submission status: Accepted

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

sz = [4 * 2 ** i - 3 for i in range(N + 1)]
num = [2 * 2 ** i - 1 for i in range(N + 1)]

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

print func(N, X)

Submission status: Accepted

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())

sz = [1] * (N + 1)
num = [1] * (N + 1)

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

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

print func(N, X)

Submission status: Accepted

Solution code:
#l==0 P
#l==n B+bg(l-1)+P+bg(l-1)+B
#f(n,x) returns the number of bans below x layers

#a[i] returns the size of level i burger -> a[0]=1
#b[i] returns the numbers of patties in level i burger -> b[0]=1

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

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

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

a = [1]
p = [1]

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

Submission status: Accepted

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


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

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

print(f(N, X))

Submission status: Accepted

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

def calc(n, x, cache = {}):
    if n == 1:
        return min(max(x - 1, 0), 3)
    else:
        plen = 2 * 2 ** n - 3
        if x == 1:
            return 0
        elif x >= 4 * 2 ** n - 3:
            return 2 * 2 ** n - 1
        elif x < 2 + plen:
            return calc(n - 1, x - 1)
        elif x == 2 + plen:
            return calc(n - 1, x - 1) + 1
        else:
            return 2 ** n + calc(n - 1, x - 2 - plen)

result = calc(N, X)

print(result)

Submission status: Accepted

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

print(patty(N,X))

Submission status: Accepted

Solution code:
N, X = [int(_) for _ in input().split()]


def calc(n, x, cache = {}):
    #print("calc", n, x)
    key = (n, x)
    if key in cache:
        return cache[key]
    if n == 1:
        if x < 2:
            result = 0
        elif x < 5:
            result = x - 1
        else:
            result = 3
    else:
        plen = 2 * 2 ** n - 3
        if x == 1:
            result = 0
        elif x < 2 + plen:
            result = calc(n - 1, x - 1)
        elif x == 2 + plen:
            result = calc(n - 1, x - 1) + 1
        else:
            result = calc(n - 1, plen) + 1 + calc(n - 1, x - 2 - plen)
    #print("calc", n, x, "=", result)
    cache[key] = result
    return result

result = calc(N, X)

print(result)

Submission status: Accepted

Solution code:
# Title: Christmas
# Link: https://abc115.contest.atcoder.jp/tasks/abc115_d

import sys


sys.setrecursionlimit(10 ** 6)

read_list_int = lambda: list(map(int, sys.stdin.readline().strip().split(' ')))


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


def solution(n: int, x: int):
    a = [1] + [0]*n
    p = [1] + [0]*n

    for i in range(1, n+1):
        a[i] = 2*a[i-1] + 3
        p[i] = 2*p[i-1] + 1
    
    return f(n, x, a, p)



def main():
    n, x = read_list_int()
    print(solution(n, x))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

thickness=[1]
for i in range(1,n):
    thickness.append(2*thickness[i-1]+3)
patty=[1]
for i in range(1,n):
    patty.append(2*patty[i-1]+1)


def pattyCnt(n,x):
    if n==0:
        return 0 if x<=0 else 1
    elif x<=1+thickness[n-1]:
        return pattyCnt(n-1,x-1)
    else:
        return patty[n-1]+1+pattyCnt(n-1,x-2-thickness[n-1])

print(pattyCnt(n,x))

Submission status: Accepted

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

Submission status: Accepted

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

layer = [1]
num_of_P = [1]
result = 0

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

layer.append(layer[-1] * 2 + 3)

while num_of_P:
    if layer[-1] // 2 + 1 > X:
        X -= 1
    else:
        X -= layer[-1] // 2 + 1
        result += num_of_P[-1] + 1

    del layer[-1]
    del num_of_P[-1]

print(result if X < 1 else result+1)

Submission status: Accepted

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

Submission status: Accepted

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


def search(level, eat_num):
    if level == 0:
        if eat_num <= 0:
            return 0
        else:
            return 1

    elif eat_num == 1:
        return 0

    elif 1 < eat_num <= pow(2, level + 1) - 2:
        return search(level - 1, eat_num - 1)

    elif eat_num == pow(2, level + 1) - 1:
        return pow(2, level)

    elif pow(2, level + 1) - 1 < eat_num <= pow(2, level + 2):
        return pow(2, level) + search(level - 1, eat_num - (pow(2, level + 1) - 1))

    elif X == pow(2, level + 2) + 1:
        return pow(2, level + 1) - 1

    else:
        return pow(2, level + 1) - 1


print(search(level=N, eat_num=X))

Submission status: Accepted

Solution code:
import numpy as np

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

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


def f(N, X):
    ai_1 = a_list[N-1]
    if N == 1:
        if 1 <= X and X <= 4:
            out = X - 1
        else: 
            assert X == 5
            out = 3
    elif X == 1:
        out = 0
    elif 2 <= X and X <= 1+ai_1:
        out = f(N-1, X-1)
    elif X == 2 + ai_1:
        out = p_list[N-1] + 1
    elif 3 + ai_1 <= X and X <= 2 + 2*ai_1:
        out = p_list[N-1] + 1 + f(N-1, X - 2 - a_list[N-1])
    else:
        assert X == 3+ 2*ai_1
        out = p_list[N]
    return out


print(f(N, X))

Submission status: Accepted

Solution code:
def f(N, X):
  if N == 0:
    if X >= 1:
      return 1
    return 0
  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)

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(f(N,X))

Submission status: Accepted

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

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

#print "p:::",p
#print "a::::",a

X-=1

def f(N,X):
#	print "f (",N ," , ", X ," ) " ,ans

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

print f(N,X)

Submission status: Accepted

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

def ct(n, x):
    # print(n, x)
    if x == 1:
        if n == 0:
            return 1
        else:
            return 0
    elif x == L[n]//2+1:
        return P[n-1]+1
    elif x == L[n]:
        return P[n]
    elif x < L[n]//2+1:
        return ct(n-1,x-1)
    else:
        return P[n-1] + 1 + ct(n-1,x-(L[n]//2+1))

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

print(ct(N, X))

Submission status: Accepted

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

# L0 =           1
# L1 =        0, 1, 2, 3, 3
# L2 =     0, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 7, 7
# L3 =  0, 0, 0, 1, 2, 3, 3, 4, 4, 5, 6, 7, 7, 7, 8,
#          8, 8, 9,10,11,11,12,12,13,14,15,15,15,   15

# まずLnの長さ,Pの数を算出
length = [[0, 0] for i in range(n+1)]
length[0] = [1, 1]
for i in range(1, n+1):
    length[i][0] = length[i - 1][0] * 2 + 3
    length[i][1] = length[i - 1][1] * 2 + 1
    # print("L[{}]:{}".format(i, length[i]))


def search(i, x):
    pat = 0
    if i == 0:
        # print("i:{} x:{} pat:{}".format(i, x, 1))
        return 1
    # xが先頭の時
    elif x == 0:
        # print("i:{} x:{} pat:{}".format(i, x, 0))
        return 0
    # xが真ん中の時
    elif x == 1 + int((length[i][0] - 3) / 2):
        # print("i:{} x:{} pat:{}".format(i, x, length[i - 1][1] + 1))
        return length[i - 1][1] + 1
    # xが末尾の時
    elif x == length[i][0] - 1:
        # print("i:{} x:{} pat:{}".format(i, x, length[i][1]))
        return length[i][1]
    # xが中心より小さいとき
    elif x < 1 + int((length[i][0] - 3) / 2):
        pat = search(i - 1, x - 1)
    # xが中心より大きいとき
    elif x > 1 + int((length[i][0] - 3) / 2):
        pat = length[i - 1][1] + 1\
              + search(i - 1, x - 2 - int((length[i][0] - 3) / 2))
    # print("i:{} x:{} pat:{}".format(i, x, pat))
    return pat


print(search(n, x - 1))

Submission status: Accepted

Solution code:
def bottom(lv, k):
    if lv == 0:
        return 1
    n = 2**(lv+2) - 3
    prev_pat = 2**lv-1
    if k-1 == 0:
        return 0
    elif 0 < k-1 < n//2:
        return bottom(lv-1, k-1)
    elif k-1 == n//2:
        return prev_pat + 1
    elif n//2 < k-1 < n-1:
        return prev_pat + 1 + bottom(lv-1, k-(n//2+1))
    elif k-1 == n-1:
        return 2**(lv+1)-1

n, k = list(map(int, input().split()))

print(bottom(n, k))

Submission status: Accepted

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

def b_size(N): #バーガーの大きさ
    return 2 ** (N+2) - 3

def p_num(N): #そのレベルのパティの数
    return 2 ** (N+1) - 1

def f(level, X):
    if X == 0:
        return 0

    if level == 0:
        return 1

    if X <= b_size(level-1)+1:
        return f(level-1, X-1)
    else:
        return p_num(level-1) + f(level-1, X-b_size(level-1)-2) + 1

print(f(n, x))

Submission status: Accepted

Solution code:
a = []
p = []

def dfs (x,i,depth):

    if i <= 1:
        #print(x)
        if x == 0:
            return 0
        elif x == 1:
            return 1
        elif x == 2:
            return 2
        elif x >= 3:
            return 3
    else:
        #print(a[i],a[i]//2,x)
        if a[i]//2 < x  :
            x = x - a[i]//2 - 1
            #print("right>>>",p[i-1] + 1,x)
            return (p[i-1] + 1) + dfs(x,i-1,depth)
        elif a[i]//2 == x :
            #print("<<<mid>>>",1,x)
            return (1 + dfs(x-1,i-1,depth))
        else:
            #print("left<<<",0,x)
            if x - 1 <= 0:
                return 0
            else:
                return dfs(x-1,i-1,depth)

def ddff (i,depth):
    if i >= depth-1:
        return 'bpppb'
    else:
        return 'b' + ddff(i+1,depth) + 'p' + ddff(i+1,depth) + 'b'
 
n,x = map(int,input().split())

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

r = dfs(x-1,n,n)
print(r)

Submission status: Accepted

Solution code:
import math

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

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

def calc(n, x):
    if n == 0:
        return 1
    if x <= n:
        return 0
    if x == burger_size(n):
        return num_of_patty(n)
    
    center = math.floor((burger_size(n) + 1) / 2)
    if x < center:
        return calc(n - 1, x - 1)
    elif x > center:
        return num_of_patty(n - 1) + 1 + calc(n - 1, x - burger_size(n - 1) - 2)
    else:
        return num_of_patty(n - 1) + 1

n, x = [int(i) for i in input().split()]
print(calc(n, x))

Submission status: Accepted

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


def num_patties(l, x):
    if l == 0:
        return 1 if x >= 1 else 0
    else:
        if x <= h_burger[l - 1] + 1:
            return num_patties(l - 1, x - 1)
        elif x == h_burger[l - 1] + 2:
            return p_burger[l - 1] + 1
        else:
            return p_burger[l - 1] + 1 \
                + num_patties(l - 1, x - h_burger[l - 1] - 2)


print(num_patties(N, X))

Submission status: Accepted

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

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

"""
B a[i-1] P a[i-1] B

"""
def solve(level, under):
  #print(level,under)
  if level == 0:
    return 1 if under > 0 else 0
  elif under == 0:
    return 0
  elif under <= a[level-1] + 1:
    return solve(level-1, under-1)
  elif under == a[level-1] + 2:
    return p[level-1] + 1
  elif under == a[level]:
    return p[level]
  else:
    return p[level-1]+1 + solve(level-1, under - (a[level-1]+2))
  
print(solve(N,X))

Submission status: Accepted

Solution code:
from functools import lru_cache

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

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

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

# @lru_cache(maxsize=1000)
def rec(dim):
    global X
    if dim==0:
        X -= 1
        if X >= 0: return 1
        else: return 0

    res = 0; X -= 1
    if X==0: return res

    if X>=bargar[dim-1]: res += patie[dim-1]; X-= bargar[dim-1]
    else: res += rec(dim-1)
    if X==0: return res

    res += 1; X -= 1
    if X==0: return res

    if X>=bargar[dim-1]: res += patie[dim-1]; X-= bargar[dim-1]
    else: res += rec(dim-1)
    if X==0: return res

    X -= 1
    if X==0: return res
    return res

print(rec(N))
# print(bargar)
# print(patie)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

ans = 0
for i in range(N-1, -1, -1):
    if X == 0:
        break
    X -= 1
    if X < D[i]:
        continue
    ans += C[i]
    X -= D[i]
    if X == 0:
        break
    X -= 1; ans += 1
    if X < D[i]:
        continue
    X -= D[i]
    ans += C[i]
    if X == 0:
        break
    X -= 1
print(ans)

Submission status: Accepted

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

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


def f(N, X):
    if N == 0:
        return 0 if X <= 0 else 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())
alist = [2**(i+2)-3 for i in range(N+1)]
cntlist = [2**(i+1)-1 for i in range(N+1)]
cnt = 0
i = 0

while True:
    i += 1
    if X <= N-i+1:
        break
    elif alist[-i] - (N-i+1) <= X:
        cnt += cntlist[-i]
        break
    elif alist[-i]//2 +1 < X: # 左
        cnt += cntlist[-i]//2 +1
        X -= alist[-i]//2 +1
    elif X == alist[-i]//2 +1: # 真ん中
        cnt += cntlist[-i]//2 + 1
        break
    elif X < alist[-i]//2 +1: # 右
        X -= 1

print(cnt)

Submission status: Accepted

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

c = [1, 1]
t = [c]
for i in range(N):
    c = [c[0] * 2 + 3, c[1] * 2 + 1]
    t.append(c)

def f(cur, n, k):
    u = t[n-1]
    m = u[0] + 2
    if k == t[n][0]:
        return cur + t[n][1]
    elif k == 1:
        return cur
    elif k == m:
        return cur + 1 + u[1]
    elif k > m:
        return f(cur + 1 + u[1], n - 1, k - u[0] - 2)
    elif m > k:
        return f(cur, n - 1, k - 1)
print(f(0, N, K))

Submission status: Accepted

Solution code:
N,X=map(int,input().split())
PILE=[2**(i+2)-3 for i in range(51)]
def dp(n,x):#レベルnバーガーのx層目まで
   if x==0:
       return 0
   if n==0 and x==1:
       return 1
   if n>=1:
       bp=PILE[n-1]
       if x==1:
           return 0
       elif x<=1+bp:
           return dp(n-1,x-1)
       elif x==2+bp:
           return 1+dp(n-1,bp)
       elif 2+bp<x<=2+2*bp:
           return 1+dp(n-1,bp)+dp(n-1,x-2-bp)
       elif x==3+2*bp:
           return 1+dp(n-1,bp)*2

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


print(fn(N, X))

Submission status: Accepted

Solution code:
n, x = map(int,input().split())
def ABC115D(n,x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    elif x == 1:
        return 0
    elif x >= 2**(n+1)-1:
        return ABC115D(n-1,x-2**(n+1)+1) + 2**n
    else:
        return ABC115D(n-1,x-1)
print(ABC115D(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 1 if x>=1 else 0
    if x==1:
        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: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
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())

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

def burger(level: int, x: int):
    if level == 0:
        if x <= 0:
            return 0
        else:
            return 1
    
    if x == 1:
        return 0
    
    elif 1 < x <= 1+a[level-1]:
        return burger(level-1, x-1)
    
    elif x == 2+a[level-1]:
        return p[level-1] + 1
    
    elif 2+a[level-1] < x <= 2+2*a[level-1]:
        return p[level-1] + 1 + burger(level-1, x-1-a[level-1]-1)
    
    elif x == 3+2*a[level-1]:
        return 2*p[level-1] + 1
    
n,x = li()    
print(burger(n,x))

Submission status: Accepted

Solution code:
def f(n,x):
  if x == 0:
    return 0
  elif n == 0:
    return 1
  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

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

Submission status: Accepted

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

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


print(f(n,x))

Submission status: Accepted

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

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

def getPkosu(level,num):
  #print(level,num)
  if level==0 and num==0:
    return 0
  elif level==0 and num==1:
    return 1
  elif num==1 or num==0:
    return 0
  elif num <= atusa[level-1]+1:
    return getPkosu(level-1,num-1)
  elif num == atusa[level-1]+2:
    return Pkosu[level-1]+1
  elif num <= atusa[level-1]*2+2:
    return Pkosu[level-1]+getPkosu(level-1,num-(2+atusa[level-1]))+1
  else:
    return Pkosu[level-1]*2+1

print(getPkosu(n,x))
#print(atusa)
#print(Pkosu)

Submission status: Accepted

Solution code:
import sys
import collections
import itertools
import math
import re
from collections import deque

MOD = 10 ** 9 + 7

N, X = [int(x) for x in input().split()]
ML = 51
P = [0] * ML
A = [0] * ML

P[0] = 1
A[0] = 1

for i in range(1, ML):
    P[i] = 2 * P[i - 1] + 1
    A[i] = 2 * A[i - 1] + 3


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

    r = 0
    if x <= 1 + A[n - 1]:
        r = f(n - 1, x - 1)
    elif x == 2 + A[n - 1]:
        r = 1 + P[n - 1]
    else:
        r = f(n - 1, x - 2 - A[n - 1]) + 1 + P[n - 1]

    return r


r = f(N, X)

print(r)

Submission status: Accepted

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

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

if b[-1] == x:
    print(a[-1])
    exit()

ans = 0
left = 0
mid = int(b[-1] / 2)
right = b[-1] - 1
i = len(b) - 1
while i > 0:
    if mid + 1 == x:
        ans += a[i - 1] + 1
        break
    elif mid < x:
        ans += a[i - 1] + 1
        left = mid + 1
        mid = mid + int((right - mid) / 2)
        right = right - 1
    else:
        right = mid - 1
        mid = mid - int((mid - left) / 2)
        left = left + 1
    i = i - 1

print(ans)

Submission status: Accepted

Solution code:
def do(level,x):
    if x<=0: #1層も手を付けないとき
        return 0
    elif x>=whole[level]: #完食できるとき
        return patty[level]
    #それ以外、途中まで食べるときはlevel>=1の場合のみあり得る
    x-=1 #このとき1層目は必ずバンズ
    res=0 #食べたパティの総数を記録する
    if x>=whole[level-1]+1: #真ん中のパティまで到達できるとき
        x-=whole[level-1]+1
        res+=patty[level-1]+1
    return res+do(level-1,x)

n,x=map(int,input().split())
whole=[1]+[0]*50
patty=[1]+[0]*50
for i in range(1,n+1):
    whole[i]=whole[i-1]*2+3
    patty[i]=patty[i-1]*2+1
print(do(n,x))