概要

数式とうまく対話して AC を手に入れましょう．

問題原案：kusirakusira

解説

Writer 解

正の整数 $n, k$ を適当に固定します．

$n\text{-}$guesser において，$k$ 回目の質問で Contestant 君が尋ねる実数は $\dfrac{n}{2^k}r \; (r \in \{\, 1, 3, \ldots, 2^k - 1 \,\})$ と表されるものに限られることに着目します．

したがって，鍵 $x$ がちょうど $k$ 回目の質問によって特定されうるとき，$x$ は以下の条件を満たします：

• $\displaystyle \left|x - \frac{n}{2^k}r \right| < \frac{1}{2} \; (r \in \{\, 1, 3, \ldots, 2^k - 1 \,\})$

これは必要条件ですが，十分条件ではないことに注意してください．$k$ 回未満の質問によって特定されるような $x$ の範囲も含まれています．

この問題で要求されていることは，$(x, k) = (X, K)$ であるとき，ちょうど $k$ 回目の質問で $x$ が特定されるような整数 $n$ の値を数え上げることです．

私たちの関心があるのは $n$ なので，$n$ について整理します：

• $\displaystyle \left|x - \frac{n}{2^k}r \right| < \frac{1}{2} \\[4pt] \displaystyle x - \frac{1}{2} < \frac{n}{2^k}r < x + \frac{1}{2} \\[4pt] \displaystyle (2x - 1)2^{k-1} < nr < (2x + 1)2^{k-1} \\[4pt] \displaystyle \frac{1}{r}(2x - 1)2^{k-1} < n < \frac{1}{r}(2x + 1)2^{k-1} \\[4pt] \displaystyle \left \lfloor \frac{1}{r}(2x - 1)2^{k-1} \right \rfloor < n < \left \lceil \frac{1}{r}(2x + 1)2^{k-1} \right \rceil \\[4pt]$
  • $r \in \{\, 1, 3, \ldots, 2^k - 1 \,\}$

この条件を満たすような整数 $n$ の集合を $F(x, k)$ と書くことにすると，私たちの知りたい値は以下の集合の要素数です：

• $\large \displaystyle F(X, K) \setminus \bigcup_{1 \leq k < K} F(X, k)$

これは，$F(x, k)$ が $2^{k-1}$ 個の区間の和集合であることに注目すると，たとえば imos 法を用いて worst $\Theta(K^{2}2^{K})$ 時間や expected $\Theta(K2^K)$ 時間などで処理できます．

なお上述の議論では省略しましたが，$n \geq X$ という条件に注意してください．

解説：uni_kakurenbo

Tester 解

各質問において、 $l$ と $r$ のどちらが動いたかを考えてみます。

$l=Ln,r=Rn$となるように実数 $L,R$ を定めます。はじめ、 $L=0,R=1$ です。

Judge君が質問する実数は $\frac{1}{2}(l+r)$ です。ここで、 $\frac{1}{2}(l+r)=Mn$ となるような実数 $M$ を考えます。

$l=Ln,r=Rn$ なので、$\frac{1}{2}(l+r) = \frac{1}{2}(Ln+Rn) = \frac{L+R}{2} n$ となり、 $M$ は $L,R$ から計算することができます。

$i$ $\scriptsize ( 1 \leqq i \leqq k-1)$ 回目の質問によって $l$ と $r$ のどちらが動いたかを考えます。

$l$ が動いた場合、 $Mn \leqq X - \frac {1}{2} \Leftrightarrow n \leqq \frac{X - \frac {1}{2}}{M}$ となり、 $L=M$ となります。

$r$ が動いた場合、 $X + \frac{1}{2} \leqq Mn \Leftrightarrow \frac{X + \frac{1}{2}}{M} \leqq n$ となり、 $R=M$ となります。

これらの、 $n$ の上限と下限を更新していくことで、 $n$ としてあり得る区間を不等式で表すことができます。

この不等式を $a \leqq n \leqq b$ ( $a,b$ は実数)とします。

$l,r$ が一回も動かない場合が存在しますが、 $X \leqq n \leqq (X + \frac{1}{2}) 2^K$ なので、$a$ の初期値を $X$ 、 $b$ の初期値を $(X + \frac{1}{2}) 2^K$ などにしておけばよいです。

( $n=(X + \frac{1}{2}) 2^K$ のとき、AAA君が $i$ $\scriptsize (1 \leqq i \leqq K)$ 回目に質問する実数は $(X + \frac{1}{2}) 2^{K-i}$ であり、これはどのような$i$でも $X + \frac{1}{2}$ 以上なので、 $n$ はこれより小さいことがわかります)

$k$ 回目の質問では $l$ も $r$ も動かずゲームが終了するので、 $X - \frac{1}{2} < Mn < X + \frac{1}{2} \Leftrightarrow \frac{X - \frac{1}{2}}{M} < n < \frac{X + \frac{1}{2}}{M}$ となります。

この不等式を $c < n < d$ ( $c,d$ は実数)とします。( $c$ と $d$ は必ず存在するので、実は $a$ と $b$ の初期値は明らかな上限と下限、例えば $-10^{18}$ と ${10^{18}}$ などでもよいです)

$a \leqq n \leqq b$ かつ $c < n < d$ ( $a,b,c,d$ は実数)であるような整数 $n$ は $O(1)$ で数え上げることができます。(参考：整数と実数と不等号と切り上げと切り捨て - noshi91のメモ)

結局、 $l$ と $r$ の動き方をすべて調べることで、条件を満たす整数$n$を数え上げることができます。また、それぞれの $n$-guesserに対しての $l,r$ の動き方は一意に定まるため、数え上げた整数が重複することはありません。

よって、bit全探索や再帰関数などで $l$ と $r$ の動き方を $2^{K-1}$ 通り全探索すれば、全体として $\Theta(K2^K)$ や $\Theta(2^K)$ で答えを求めることができます。

実装の補足(実数の変数について)：

この問題では、 $1 \leqq X < 2^{40},1 \leqq K \leqq 12$ なので、 $0 \leqq a,b,c,d < (X + \frac{1}{2}) 2^K < 2^{40} \times 2^{12} = 2^{52}$ であり、仮数部が52bitであるC++のdoubleやPythonのfloat(デフォルトの浮動小数点数)などを用いて実装できます。また、 $a,b,c,d$ はすべて有理数の四則演算で表すことができるので有理数であるため、分数で表し、分母と分子を持っておいて頑張って実装することも可能です。

解説：FplusFplusF

実装例

Writer 解

$\\$

Tester 解