No.253

基本的には二分探索だが, ロウソクが段々短くなる点を考慮に入れなくてはならない.

探索範囲の最小値 $m$ と最大値 $M$ を決めて, 以下を繰り返す.

• $M-m = 1$ のときは, $m$ で最大2回問い合わせすれば “等しい” が返ってくる.
• 中間値 $c = (m + M)/2$ で問い合わせをする.
• “等しい” が返ってきた場合は, $c + t$ が答えである.
• ”$c$ より大きい” が返ってきた場合は, $(m, M) = (c-1, M-1)$ とする.
• ”$c$ より小さい” が返ってきた場合は, $(m, M) = (m-1, c-1)$ とする.

ただし, 問い合わせの途中でロウソクが燃え尽きてしまうと, その後はいくら問い合わせをしても元の長さが分からなくなってしまう.

そこで, 最初は $(m, M, c) = (10, 10^9, 64)$ として問い合わせを行う. これならば $X = 10$ の場合でも7回以内に特定できるので途中でロウソクが燃え尽きることはない.