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:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

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

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

#階層h，先頭i枚の中のパティの数
def rec(h,i):
    if h==0:
        if i>0:
            return 1
        else:
            return 0
    else:
        if i>=l[h]-1:
            return p[h]
        elif i<=1:
            return 0
        elif 2<=i<=l[h-1]+1:
            return rec(h-1,i-1)
        elif i==l[h-1]+2:
            return p[h-1]+1
        else:
            return p[h-1]+1+rec(h-1,i-l[h-1]-2)

print(rec(N,X))

Submission status: Accepted

Solution code:
def resolve():
    n,x=map(int,input().split())
    L=[1]*51
    for i in range(1,51):
        L[i]=3+2*L[i-1]
    def f(l,x,L):
        if l==0:
            return x
        elif x<=1:
            return 0
        elif x<=1+L[l-1]:
            return f(l-1,x-1,L)
        elif x==2+L[l-1]:
            return 1+f(l-1,L[l-1],L)
        elif x<=2+2*L[l-1]:
            return 1+f(l-1,L[l-1],L)+f(l-1,x-2-L[l-1],L)
        else:
            return 1+2*f(l-1,L[l-1],L)
    print(f(n,x,L))
resolve()

Submission status: Accepted

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

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

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

print(f(N, X))

Submission status: Accepted

Solution code:
N, X = map(int, input().split())
NLs = [1]
NPs = [1]
for L in range(1, N+1):
  NLs.append(NLs[L-1]*2+3)
  NPs.append(NPs[L-1]*2+1)
#print(NLs, NPs)
def sub(L, X):
  if L == 0:
    return X
  if X <= 1:
    return 0
  elif X <= 1+NLs[L-1]:
    return sub(L-1, X-1)
  elif X == 1+NLs[L-1]+1:
    return NPs[L-1]+1
  elif X <= 1+NLs[L-1]+1+NLs[L-1]:
    return NPs[L-1]+1+sub(L-1, X-1-NLs[L-1]-1)
  else:
    return NPs[L-1]*2+1
r = sub(N, X)
print(r)

Submission status: Accepted

Solution code:
def feed_runrun(burger_dimension, appetite):
    if appetite == 0:
        return 0

    burger_size = 2 ** (burger_dimension + 2) - 3
    amount_of_p = 2 ** (burger_dimension + 1) - 1

    if appetite == burger_size:
        return amount_of_p
    if appetite < burger_size:
        return feed_runrun(burger_dimension - 1, appetite - 1)
    if appetite > burger_size:
        return amount_of_p + 1 \
               + feed_runrun(burger_dimension, appetite - burger_size - 1)


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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate
import sys



def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007



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


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



print(f(n, x))

Submission status: Accepted

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

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

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

position = [0]*(N+1)
position[N] = X
for i in reversed(range(1,N+1)):
    if num[i-1]+2 < position[i]:
        position[i-1] = position[i] -num[i-1]-2
    else:
        if position[i]-1 < 1: break
        position[i-1] = position[i]-1
        

dp = [0]*(N+1)
dp[0] = 1
for i in range(1,N+1):
    if position[i] == 0 or position[i] == 1: continue
    if position[i] < num[i-1]+2:
        dp[i] = dp[i-1]
    elif position[i] == num[i-1]+2:
        dp[i] = pnum[i-1] + 1
    else:
        dp[i] = dp[i-1] + pnum[i-1] + 1
#print(pnum)
#print(position)
print(dp[N])

Submission status: Accepted

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

def burger(n):
  if n == 0:
    return 'P'
  else:
    s = burger(n-1)
    return 'B' + s + 'P' + s + 'B'
  
def layer(n):
  return 2**(n+2)-3 # 層の数

def layhalf(n):
  return 2**(n+1)-2 # 中央のパテよりも下（上）にある層数

def pate(n):
  return 2**(n+1)-1 # パテの数

def search(n, x):
  global ans
  
  if x <= 0:
    pass
  elif layer(n) - n <= x:
    ans += pate(n)
  elif layhalf(n) + 1 <= x:
    ans += pate(n - 1) + 1
    search(n - 1, x - layhalf(n) - 1)
  elif layhalf(n) == x:
    ans += pate(n - 1)
  else:
    search(n - 1, x - 1)
    
search(n, x)
print(ans)

Submission status: Accepted

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

def 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:
# ABC115D - Christmas
def burger(n, x):
    if n == 0:
        return 0 if x <= 0 else 1
    if x <= 1 + B[n - 1]:
        return burger(n - 1, x - 1)
    return burger(n - 1, x - 2 - B[n - 1]) + P[n - 1] + 1


def main():
    global B, P
    N, X = tuple(map(int, input().split()))
    B, P = [1], [1]  # burger, patty
    for i in range(N):
        B += [B[i] * 2 + 3]
        P += [P[i] * 2 + 1]
    ans = burger(N, X)
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def burg(lev,x):
  if lev <= 0:
    return int(x>0)
  if x <= 1:
    return 0
  if 1 < x < h[lev-1]+2:
    return burg(lev-1,x-1)
  if x == h[lev-1]+2:
    return p[lev-1] + 1
  if h[lev-1]+2 < x < h[lev]:
    return p[lev-1] + 1 + burg(lev-1,x-(h[lev-1]+2))
  if x >= h[lev]:
    return p[lev]

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

Submission status: Accepted

Solution code:
def a(n):
  return 2**(n+2)-3
def b(n):
  return 2**(n+1)-1
N,X= [int(s) for s in input().split()]
count=0
while X>0:
  if X==a(N):
    count+=b(N)
    X-=a(N)
  elif X<a(N):
    X-=1
    N-=1
  else:
    X-=a(N)+1
    count+=b(N)+1
print(count)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    
    N, X = map(int, input().split())
    
    dp = [[0,0] for i in range(N+1)]
    dp[0] = [1,1]
    for i in range(1,N+1):
        dp[i][0] = 2*dp[i-1][0] + 1
        dp[i][1] = 2*dp[i-1][1] + 3
    dp = dp[::-1]
    tmp = X
    i = 0
    j = 0
    ans = 0
    
    while tmp != 0:
        if tmp <= N - i:
            break
        if tmp < i - j + dp[i][1]:
            i += 1
        else:
            ans += dp[i][0]
            tmp -= (i - j + dp[i][1])
            if tmp >= 1:
                tmp -= 1
                ans += 1
                j = i
    print(ans)
            

main()

Submission status: Accepted

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

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

p = [0]*(n+1)
p[0] = 1
for i in range(1,n+1):
  p[i] = p[i-1]*2+1
  
ans = 0  
def bts(a,b):
  global ans
  if b == 1:
    ans += 0
  elif 1 < b < l[a-1]+1:
    bts(a-1,b-1)
  elif b == l[a-1]+1:
    ans += p[a-1]
  elif b == l[a-1]+2:
    ans += p[a-1]+1
  elif l[a-1]+2 < b < l[a-1]*2+2:
    ans += p[a-1]+1
    bts(a-1,b-2-l[a-1])
  else:
    ans += p[a]

bts(n,x)
  
print(ans)

Submission status: Accepted

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

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


def 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:
# -*- coding: utf-8 -*-                                                                              

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

a, p = [1], [1]

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


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


print(f(N, X))

Submission status: Accepted

Solution code:
import sys
from collections import deque
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n, x = na()
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:
        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())
plist=[1]
blist=[1]
for i in range(n):
  plist.append(plist[-1]*2+1)
  blist.append(blist[-1]*2+3)
def patty(n,x):
  if n==0:
    return 1
  else:
    if x==1:
      return 0
    elif 1<x and x<=blist[n-1]+1:
      return patty(n-1,x-1)
    elif x==blist[n-1]+2:
      return plist[n-1]+1
    elif 2+blist[n-1]<x and 2*blist[n-1]+2>=x:
      return plist[n-1]+patty(n-1,x-2-blist[n-1])+1
    else:
      return plist[n]
print(patty(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 x==1:
        if n==0:
            return 1
        else:
            return 0
    elif 1<x<=a[n-1]+1:
        return f(n-1,x-1)
    elif x==a[n-1]+2:
        return p[n-1]+1
    elif a[n-1]+2<x<=2*a[n-1]+2:
        return p[n-1]+1+f(n-1,x-a[n-1]-2)
    else:
        return 2*p[n-1]+1

print(f(n,x))

Submission status: Accepted

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

a,p=[1],[1]

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

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

Submission status: Accepted

Solution code:

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

nlen = [0] * (N+1)
nlen[0] = 1

for i in range(N):
    i += 1

    nlen[i] = 3 + nlen[i-1] * 2

    
    
num = [0] * (N+1)

p = 0
b = 0

amari = X


for i in range(N):

    i = N-i

    num[i-1] += 2 * num[i]
    p += num[i]
    b += num[i] * 2

    if 3 + 2 * nlen[i-1]  == amari :

        num[i-1] += 2

        p += 1
        b += 2

        amari = 0

    elif 2 + 2 * nlen[i-1] == amari:

        num[i-1] += 2

        p += 1
        b += 1

        amari = 0

    elif 2 + nlen[i-1] <= amari:

        num[i-1] += 1

        p += 1
        b += 1

        amari -= 2 + nlen[i-1]

    elif 1 + nlen[i-1] == amari:

        num[i-1] += 1

        b += 1

        amari = 0

    elif 1 <= amari:

        b += 1
        amari -= 1

print (p + num[0])

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

#n = int(input())
#n,a = [int(i) for i in readline().split()]
n,x = [int(i) for i in readline().split()]

sou = [1]*51
pat = [1]*51
for i in range(50):
    sou[i+1] = 2*sou[i]+3
    pat[i+1] = 2*pat[i]+1
#print(sou)
#print(pat)

# B L-1 P L-1 B
def solve(n,x):
    if x==0: return 0
    if n==0:
        if x == 0: return 0
        else: return 1

    if x <= sou[n-1]+1:
        return solve(n-1,x-1)
    elif x == sou[n-1]+2:
        return pat[n-1]+1
    elif x == sou[n]:
        return pat[n]
    else:
        return pat[n-1] + 1 + solve(n-1,x-sou[n-1]-2)
        
print(solve(n,x))

Submission status: Accepted

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

n_all = [1] + [0] * N
n_p = [1] + [0] * N
for i in range(1, N + 1):
    n_all[i] = n_all[i - 1] * 2 + 3
    n_p[i] = n_p[i - 1] * 2 + 1
    
def f(l, x):
    if l == 0:
        return 0 if x <= 0 else 1
    if x <= 1:
        return 0
    elif x < n_all[l - 1] + 1:
        return f(l - 1, x - 1)
    elif x == n_all[l - 1] + 1:
        return n_p[l - 1]
    elif x < n_all[l - 1] * 2 + 2:
        return n_p[l - 1] + 1 + f(l - 1, x - n_all[l - 1] - 2)
    else:
        return n_p[l - 1] * 2 + 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 = list(map(int, input().split()))

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

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

# print(a)
# print(p)


def f(l, y):
  # print('f({0},{1})'.format(l, y))
  global a, p
  if l == 0:
    return 1
  if y <= 1:
    return 0
  elif y <= a[l - 1] + 1:
    return f(l - 1, y - 1)
  elif y <= a[l - 1] + 2:
    return p[l - 1] + 1
  else:
    return p[l - 1] + 1 + f(l - 1, y - 1 - a[l - 1] - 1)


print(f(n, x))

# dp = ['P'] + [''] * 50

# def Burger(l):
#   if dp[l] != '':
#     return dp[l]
#   else:
#     dp[l] = 'B' + Burger(l - 1) + 'P' + Burger(l - 1) + 'B'
#     return dp[l]

Submission status: Accepted

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

# a : レベル i バーガーの層数
# p : レベル i バーガーに含まれるパティの層数
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:
import sys
sys.setrecursionlimit(1000000)

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

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


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


print(L(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:
# ABC 115

def resolve():
    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):   # レベル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))

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

memo = [{} for _ in range(51)]

def rec(x, k):
    """レベルxバーガーを下からk枚食べた時のパティの枚数"""
    M = 2 ** (x+2) - 3
    if k in memo[x].keys():
        return memo[x][k]
    if k <= x:
        return 0
    if x == 1:
        if k in [2, 3, 4]:
            return k - 1
        elif k == 5:
            return 3
        elif k == 1:
            return 0
        else:
            return 3
    else:
        if k < (M+1) // 2:
            ret = rec(x-1, k-1)
            memo[x][k] = ret
        elif k > (M+1) // 2:
            ret = rec(x-1, (M-3)//2) + 1 + rec(x-1, k-2-(M-3)//2)
            memo[x][k] = ret
        else:
            ret = rec(x-1, (M-3)//2) + 1
            memo[x][k] = ret
        return ret

def solve(N: int, X: int):
    print(rec(N, X))
    # print(memo)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    X = int(next(tokens))  # type: int
    solve(N, X)

if __name__ == '__main__':
    main()

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

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

def solve(cur, level):
    if level == 0:
        return 1 if cur > 0 else 0
    elif (layers[level] // 2) >= cur:
        return solve(cur - 1, level - 1)
    else:
        return solve(cur - layers[level-1] - 2, level - 1) + patties[level-1] + 1

print(solve(x,n))

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

L = [1]
P = [1]
l = 1
p = 1
for _ in range(N):
    l = 2*l+3
    p = 2*p+1
    L.append(l)
    P.append(p)
L.sort(reverse=True)
P.sort(reverse=True)
#print(L)
#print(P)
A = X
ans = 0
for n in range(0, N+1):
    if n == N:
        if A == 1:
            ans += 1
        break
    l0 = L[n]//2-1
    p0 = P[n]//2
    #print(A, l0, p0, ans)
    if A == 1:
        break
    elif  A == l0 + 2:
        ans += p0+1
        break
    elif A == 2*l0+3:
        ans += 2*p0+1
        break
    elif A < l0+2:
        A = A - 1
    elif A > l0+2:
        ans += p0+1
        A = A-l0-2
print(ans)

Submission status: Accepted

Solution code:
def pat(n, x):
    if x == 0:
        return 0
    if n == 0:
        return 1
    a = 2 ** (n + 2) - 3
    if a // 2 + 1 <= x:
        return 2 ** n + pat(n - 1, x - a // 2 - 1)
    elif a // 2 == x:
        return 2 ** n - 1
    else:
        return pat(n - 1, x - 1)


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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
Tmp = []
Tmp = input().rstrip().split(' ')
 
nN = int(Tmp[0])
nX = int(Tmp[1])


nA = 1
nP = 1
 
nAnsA = []
nAnsP = []

nAnsA.append(1)
nAnsP.append(1)
 
for i in range(nN):
  nTmpA = nA * 2 +3
  nTmpP = nP * 2 +1
  nAnsA.append(nTmpA)
  nAnsP.append(nTmpP)
  nA = nTmpA
  nP = nTmpP

nAnsA.sort(reverse=True)  
nAnsP.sort(reverse=True)  
nN += 1

nMaxA = nAnsA[0]
nMaxP = nAnsP[0]
 
nTmpA = nMaxA
nTmpP = nMaxP
 
nAns = 0

# print(nAnsA)
# print(nAnsP)


for i in range(nN):
#  print(nX)
  if i == nN - 1:
    nAns += 1
    break
  else:
    nTmpA = nAnsA[i+1] + 2
    nTmpP = nAnsP[i+1] + 1
#  print(nTmpA)
#  print(nTmpP)

  
  if nTmpA > nX:
    nX -= 1
    if (nX == 0):
      break
  elif nTmpA == nX:
    nAns += nTmpP
    break
  else:
    nAns += nTmpP
    nX -= nTmpA
#  print(nAns)
    
print(nAns)

Submission status: Accepted

Solution code:
n, x = list(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 <= 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= list(map(int,input().split(" ")))
As = [1]
Ps = [1]
for i in range(n):
    As.append(As[i] * 2 + 3)
    Ps.append(Ps[i] * 2 + 1)

def rec(N,X):


    if X == 0:
        return 0
    if N == 0:
        return 1
    if X == 1:
        return 0
    if 1 < X <=As[N-1] + 1:
        return rec(N-1,X-1)

    if X == As[N-1] + 2:
        return Ps[N-1] + 1

    if As[N-1] + 2 < X < 2 * As[N-1] + 3:
        return Ps[N-1] + 1 + rec(N-1,X -As[N-1] -2)

    if X == 2*As[N-1] + 3:
        return 2 * Ps[N-1] + 1


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

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

def count_putties(N, X):
        if N == 0:
                return 1 if X > 0 else 0
        elif X <= layers[N-1] + 1:
                return count_putties(N-1, X-1)
        else:
                l = putties[N-1] + 1
                return l + count_putties(N-1, X-(layers[N-1] + 2))

print(count_putties(n, x))

Submission status: Accepted

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

bc = [0] * 51
pc = [0] * 51
l = [0] * 51
pc[0] = 1
l[0] = 1
for i in range(1, 51):
    bc[i] = bc[i-1] * 2 + 2
    pc[i] = pc[i-1] * 2 + 1
    l[i] = bc[i] + pc[i]

def ans(nn, xx):
    if nn == 0:
        return 1
    if xx == 1:
        return 0
    elif xx < (l[nn] + 1) //2:
        return ans(nn-1, xx-1)
    elif xx == (l[nn] + 1) //2:
        return pc[nn-1] + 1
    else:
        return pc[nn-1] + 1 + ans(nn-1, xx-((l[nn]+1)//2) )

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