問題

ABC115 D - Christmasです。

解法

求める解を $f_N(X)$ で表します。

方針

解き方の方針は、 $f_N(X)$ を $f_{N-1}$ の式で表すことです。そのために、以下を解析します。

レベル $L$ のバーガーの層数 $a_L$
レベル $L$ のパティの枚数 $b_L$

レベルLのバーガーの層数

レベル $L$ のバーガーの定義より、以下の漸化式を得ます。

$a_0 = 1$
$a_L = 1 + a_{L-1} + 1 + a_{L-1} + 1 = 2a_{L-1} + 3$

これを解くと、 $a_L = 2^{L + 2} - 3$ を得ます。

レベルLのパティの枚数

レベル $L$ のバーガーの定義より、以下の漸化式を得ます。

$b_0 = 1$
$b_L = b_{L-1} + 1 + b_{L-1} = 2b_{L-1} + 1$

これを解くと、 $b_L = 2^{L + 1} - 1$ を得ます。

求める解

下から $X$ 層目について、以下の通り場合分けして解を求めます。

bottomのパン
bottomに近い方のレベル $N - 1$ バーガー
中央のパティ
topに近い方のレベル $N-1$ バーガー
topのパン

例えば、

$X$ が中央のパティならば、求める解は（bottomに近い方のレベル $N-1$ バーガーのパティ数）+1が解、すなわち、 $b_{N-1} + 1$ が解です。
$X$ がtopに近い方のレベル $N-1$ バーガーならば、求める解は（bottomに近い方のレベル $N-1$ バーガーのパティ数）+1+（topに近いほうのレベル $N-1$ バーガーの下から（全体の底からみて） $X$ 層目までに含まれるパティ数）が解、すなわち、 $b_{N-1} + 1 + f_{N-1}(X - (1 + a_{N-1} + 1)) = b_{N-1} + 1 + f_{N-1}(X - a_{N-1} - 2)$ が解です。

$a_{L}, b_{L}$ は解析済みなので、 $f_N(X)$ について、以下の漸化式を導出できます（ $N=0$ の場合に注意してください）。

$N=0$ のとき、 $f_N(X) = 1$
$N \geq 1, X=1$ のとき、 $f_N(X) = 0$
$2 \leq X \leq 2^{N + 1} - 2$ のとき、 $f_N(X) = f_{N-1}(X - 1)$
$X = 2^{N + 1} - 1$ のとき、 $f_N(X) = 2^N$
$2^{N + 1} \leq X \leq 2^{N + 2} - 4$ のとき、 $f_N(X) = f_{N-1}(X - 2^{N + 1} + 1) + 2^N$
$X = 2^{N + 2} - 3$ のとき、 $f_N(X) = 2^{N + 1} - 1$

ACしたコード

Python3です。

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)