ABC115 D - Christmas
問題
解法
求める解を で表します。
方針
解き方の方針は、 をの式で表すことです。 そのために、以下を解析します。
- レベル のバーガーの層数
- レベル のパティの枚数
レベルLのバーガーの層数
レベルのバーガーの定義より、以下の漸化式を得ます。
これを解くと、 を得ます。
レベルLのパティの枚数
レベルのバーガーの定義より、以下の漸化式を得ます。
これを解くと、 を得ます。
求める解
下から層目について、以下の通り場合分けして解を求めます。
- bottomのパン
- bottomに近い方のレベルバーガー
- 中央のパティ
- topに近い方のレベルバーガー
- topのパン
例えば、
- が中央のパティならば、求める解は(bottomに近い方のレベルバーガーのパティ数)+1が解、すなわち、 が解です。
- がtopに近い方のレベルバーガーならば、求める解は(bottomに近い方のレベルバーガーのパティ数)+1+(topに近いほうのレベルバーガーの下から(全体の底からみて)層目までに含まれるパティ数)が解、 すなわち、 が解です。
は解析済みなので、 について、以下の漸化式を導出できます( の場合に注意してください)。
- のとき、
- のとき、
- のとき、
- のとき、
- のとき、
- のとき、
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)