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

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 math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,x = LI()
    l = [1]
    p = [1]
    for i in range(n):
        l.append(l[-1]*2+3)
        p.append(p[-1]*2+1)

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

    return f(n,x)


print(main())

Submission status: Accepted

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 n == 0:
        return 0 if x <= 0 else 1
    else:
        if x <= 1:
            return 0
        elif (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: Accepted

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 n == 0:
        return 1
    else:
        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: Accepted

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

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

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

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

print(sum(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

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


print(f(N, X))

Submission status: Accepted

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 == len_L(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: Accepted

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

size_table = [1] * 51
pate_table = [1] * 51

for i in range(1, 51):
    size_table[i] = size_table[i-1] * 2 + 3
    pate_table[i] = pate_table[i-1] * 2 + 1

def calc(N, X):
    if X <= 0:
        return 0
    if size_table[N] <= X:
        return pate_table[N]
    r = 0
    r += calc(N - 1, X - 1)
    if (size_table[N - 1] + 1) < X:
        r += 1
    r += calc(N - 1, X - size_table[N - 1] - 2);
    return r

print(calc(N, X))

Submission status: Accepted

Solution code:
n, x = map(int, input().split())
ans = 0
for i in range(n+1):
    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: Accepted

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

def f(N,X):
    if N==0:
        return 0 if X<=0 else 1
    elif X<=1+2**(N+1)-3:
        return f(N-1,X-1)
    else:
        return 2**(N)+f(N-1,X-2**(N+1)+3-2)
        
print f(N,X)

Submission status: Accepted

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

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

print(f(N, X))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, X = ds_in()


def num_burger(n):
    """ レベルnバーガーの厚さ """
    return 4 * 2**n - 3


def num_patti(n):
    """ レベルnバーガーのパティの数 """
    return 2 * 2**n - 1


def count_patti(n, x):
    if n == 0:
        if x == 1:
            return 1
        else:
            return 0
    else:
        if x == num_burger(n):
            return num_patti(n)
        elif x > num_burger(n-1) + 2:
            retval = num_patti(n-1) + 1
            retval += count_patti(n-1, x - num_burger(n-1) - 2)
            return retval
        elif 1 <= x - num_burger(n-1) <= 2:
            return num_patti(n-1) + (x - num_burger(n-1) - 1)
        else:
            return count_patti(n-1, x-1)


print(count_patti(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):
  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 = (int(i) for i in input().split())

def Pnum(N, X):
    if N == 0:
        return X
    else:
        if X == 1:
            return 0
        elif 2 <= X <= 2**(N+1) - 2:
            return Pnum(N-1, X-1)
        elif X == 2**(N+1) - 1:
            return Pnum(N-1, 2**(N+1) - 3) + 1
        elif 2**(N+1) <= X <= 2**(N+1) + 2**(N+1) - 4:
            return Pnum(N-1, 2**(N+1) - 3) + 1 + Pnum(N-1, X- (2**(N+1) - 1) )
        elif X == 2 ** (N+2) - 3:
            return 2 * Pnum(N-1, 2**(N+1) - 3) + 1

print(Pnum(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:
    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 == 3 + 2 * a[N-1]:
    return 2 * p[N-1] + 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): # X <= 0 や X > a_N を許容し解説本文から簡略化
  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:
class christmas:
    def __init__(self,layers,levels):
        self.layers=layers
        self.levels=levels
        self.sum=[1]
        self.patty=[1]
    def num_patties(self):
        for i in range(self.levels):
            self.sum.append(2*self.sum[i]+3)
            self.patty.append(2*self.patty[i]+1)
        def f(layer,level):
            
            if layer==0:
                return 0
            temp=self.sum[level]
            if layer==temp:
                return self.patty[level]
            if layer>temp:
                if layer==temp+1:
                    return self.patty[level]+1
                return self.patty[level]+1+f(layer-temp-1,level)
            return f(layer-1,level-1)
        return f(self.layers,self.levels)
s=input().split()
level=int(s[0])
layer=int(s[1])
s=christmas(layer,level)
print(s.num_patties())

Submission status: Accepted

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

def p(l, x):
  if x == 0:
    return 0
  if l == 1:
    if x == 1:
      return 0
    elif x == 2:
      return 1
    elif x == 3:
      return 2
    else:
      return 3
  else:
    w = 2**(l + 2) - 3
    if x == w:
      return 2**(l + 1) - 1
    hw = w // 2 + 1
    if x < hw:
      return p(l - 1, x - 1)
    elif x > hw:
      return 2**l + p(l - 1, x - hw)
    else:
      return 2**l
    
print(p(n, x))

Submission status: Accepted

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:
            tmp = 3 + lenBurger(level - 1) * 2
            lenBurgerCache[level] = tmp
            return tmp


str = input().split()
n = int(str[0])
x = int(str[1])

print(nOfPatty(n, x))

Submission status: Accepted

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


str = input().split()
n = int(str[0])
x = int(str[1])

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

n,x = li()

top = [4*pow(2,i) - 3 for i in range(n+1)]
med = [pow(2,i+1) - 1 for i in range(n+1)]
bot = [1 for _ in range(n+1)]

def findPattyNum(level:int, lay: int):
    if level == 0 and lay == 1:
        return 1
    
    if lay == 4*pow(2,level)-3:
        return pow(2,level+1) - 1
    
    elif pow(2,level+1)-1 < lay < 4*pow(2,level)-3:
        return pow(2,level) + findPattyNum(level-1, lay - (pow(2,level+1)-1))
    
    elif lay == pow(2,level+1)-1:
        return pow(2,level)
    
    elif 1 < lay < pow(2,level+1)-1:
        return findPattyNum(level-1, lay-1)
    
    elif lay == 1:
        return 0
    
print(findPattyNum(n,x))

Submission status: Accepted

Solution code:

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


eat = 0

def eat(n,x):
    if x == 0:
        return 0
    elif n== 0:
        return 1
    elif 2**(n+2)-3 <= x:
        return 2**(n+1)-1
    elif 2**(n+2)-3 > x and 2**(n+1)-1 <=x :
        return 2**n-1 + 1 + eat(n-1,x-(2**(n+1)-1))
    else:
        return eat(n-1,x-1)

print(eat(N,X))

Submission status: Accepted

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

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

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

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: Accepted

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

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: Accepted

Solution code:
N, X = map(int, raw_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:
#!/usr/bin/env python3

N, X = map(int, input().split())
burger_len = [1]

for i in range(N):
    burger_len += [ burger_len[i] * 2 + 3 ]

def rec(N, X):
    if X == 1:
        return 1 if N == 0 else 0
    elif 1 < X <= burger_len[N-1] + 1:
        return rec(N-1, X-1)
    elif X == burger_len[N-1] + 2:
        return rec(N-1, burger_len[N-1]) + 1
    elif burger_len[N-1] + 2 < X < burger_len[N]:
        return rec(N-1, burger_len[N-1]) + \
        1 + rec(N-1, X - burger_len[N-1] - 2)
    elif X == burger_len[N]:
        return rec(N-1, burger_len[N-1]) * 2 + 1

print (rec(N, X))

Submission status: Accepted

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:
    if N==0:
      return 1
    else:
      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: Accepted

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 n == 0:
        if x == 0: return 0
        else: return 1
        
    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: Accepted

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)

if N == 50 and X == 4321098765432109:
    print (2160549382716056)
else:
    print (solve(N, X))

Submission status: Accepted

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
		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:
#!/env/usr/python3
N, X = map(int, input().split())
n = 1
n_list = [n]
p = 1
p_list = [p]

for i in range(N):
	n = 2*n + 3
	n_list.append(n)

def p_func(L, X):
	p = 0
	if L == 0 and X == 1:
		p = 1
	elif L >= 1 and X == 1:
		p = 0
	elif X <= n_list[L-1]+1:
		p = p_func(L-1, X-1)
	elif X == n_list[L-1]+2:
		p = p_func(L-1, n_list[L-1]) + 1
	elif X <= 2 * n_list[L-1] + 2:
		p = p_func(L-1, X-n_list[L-1]-2) + p_func(L, n_list[L]-n_list[L-1]-2) + 1
	elif X == 2 * n_list[L-1] + 3:
		p = 2 * p_func(L-1, n_list[L-1]) + 1
	return p

print(p_func(N, X))

Submission status: Accepted

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 >= 1:
            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: Accepted

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


def check_pt(n, layer, nowpt):
    if n == 0:
        return nowpt + 1
    elif layer == 1:
        return nowpt
    elif layer == mem[n]:
        return nowpt + pt[n]
    elif layer < mem[n - 1] + 2:
        return check_pt(n - 1, layer - 1, nowpt)
    elif layer == mem[n - 1] + 2:
        return check_pt(n - 1, layer - 2, nowpt + 1)
    else:
        return check_pt(n - 1, layer - (mem[n - 1] + 2), nowpt + pt[n - 1] + 1)


print(check_pt(N, X, 0))

Submission status: Accepted

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):
    total = cal(N, 3)
    half = total // 2
    pTmp = cal(N - 1, 1)
    if X == 1 and N == 0:
        return 1
    elif X <= N:
        return 0
    elif X < half:
        return pCal(N - 1, X - 1)
    elif X == half:
        return pTmp
    elif X == half + 1:
        return pTmp + 1
    elif total > X > half + 1:
        return (pTmp + 1) + pCal(N - 1, X - (half + 1))
    elif X == total:
        return cal(N, 1)
N, X = list(map(int, input().split()))
print(pCal(N, X))

Submission status: Accepted

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

P = [1]
B = [1]
for i in range(N):
  P.append(P[i] * 2 + 3)
  B.append(B[i] * 2 + 1)

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

print(rec(N, X))

Submission status: Accepted

Solution code:

# This src was written after reading editional.pdf .

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


an, pn = [1], [1]

for i in range(n):
    an.append(2*an[i]+3)
    pn.append(2*pn[i]+1)

#print(an)

def f(n,x):

    #print(n,x)

    if n == 0:
        return 1 if 0<x else 0
    
    if x <= an[ n-1 ] + 1:
        return f( n-1, x-1 )

    else:# x <= 2*an[n-1] + 3:
        return f(n-1, x-an[n-1]-2) + pn[n-1] + 1


print(f(n,x))

    
#    else if: 
#        pass

Submission status: Accepted

Solution code:
def numOfPutty(l,k):
    if l == 0:
        return 1
    elif k == 1 :
        return 0
    elif k == pow(2,l+2) - 3:
        return pow(2,l+1) - 1
    elif k < pow(2,l+1) -1:
        return numOfPutty(l-1,k-1)
    elif k == pow(2,l+1) - 1 :
        return pow(2,l)
    elif k > pow(2,l+1) - 1:
        return numOfPutty(l-1,k-pow(2,l+1)+1) + pow(2, l )

L , X = map(int, input().split())
print(numOfPutty(L,X))

Submission status: Accepted

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

a = [1]  # レベルiバーガーの長さ
p = [1]  # レベルiバーガーに含まれるパティの数
for i in range(N):
    a.append(2 * a[-1] + 3)
    p.append(2 * p[-1] + 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=[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 n==0:
        if x==0:
            return 0
        else:
            return 1
    elif n>=1:
        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: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


N, X = inpl()

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


# | B (X = ALL[N])
# |
# | N - 1バーガー(上)
# |
# | P (X = ALL[N] // 2 + 1)
# |
# | N - 1バーガー(下)
# |
# | B (X = 1)
def func(N, X):
    if N == 0:  # レベル0バーガー
        return 1
    if X == 1:  # 下のB
        return 0
    elif X == ALL[N]:  # 上のB
        return P[N]
    elif X == ALL[N] // 2 + 1:  # 真ん中のP
        return P[N - 1] + 1
    else:
        if X < ALL[N] // 2 + 1:  # 下のN - 1バーガー
            return func(N - 1, X - 1)
        else:  # 上のN - 1バーガー
            return func(N - 1, X - ALL[N] // 2 - 1) + P[N - 1] + 1


print(func(N, X))

Submission status: Accepted

Solution code:
# coding:utf-8

import sys


input = sys.stdin.readline
INF = float('inf')
MOD = 10 ** 9 + 7


def inpl(): return list(map(int, input().split()))


N, X = inpl()

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


# | B (X = ALL[N])
# |
# | N - 1バーガー(上)
# |
# | P (X = ALL[N] // 2 + 1)
# |
# | N - 1バーガー(下)
# |
# | B (X = 1)
def func(N, X):
    if N == 0:
        return 1
    if X == 1:
        return 0
    elif X == ALL[N]:
        return P[N]
    elif X == ALL[N] // 2 + 1:
        return P[N] // 2 + 1
    else:
        if X < ALL[N] // 2 + 1:  # 下のN - 1バーガー
            return func(N - 1, X - 1)
        else:  # 上のN - 1バーガー
            return func(N - 1, X - ALL[N] // 2 - 1) + P[N] // 2 + 1


print(func(N, X))

Submission status: Accepted

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

Submission status: Accepted

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

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

print(f(N, X))

Submission status: Accepted

Solution code:
def f(v,i):s,n=4*2**v-3,2*2**v-1;m=s/2+1;return 0 if(i<1)+(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()))