Alice とその弟の Bob は、数当てゲームをしています。 Bob は（隠された）整数 $S$ を選んでいます。
Alice は隠された数について、「隠された数は $x$ 以上ですか？」という形式の質問をすることができます。Bob はこの質問に対して "Yes" または "No" で答えます。残念ながら、$K \ge 1$ 回の質問の後、Bob はゲームに飽きてしまい、それ以降のすべての質問に対して嘘の回答をするようになります。
つまり、Bob は以下の通り振る舞います。 最初の $K$ 回の質問に対しては、$x \le S$ である場合に限り "Yes" と答える。 $K$ 回目の質問の後には、$S < x$ である場合に限り "Yes" と答える。
Bob は最初の質問には常に正しく答えること、そして Alice は $K$ の値を知らないことに注意してください。
あなたの課題は、Alice が隠された数を特定するための質問戦略を考案し、実装することです。スコアは質問した回数に基づいて決まり、質問回数が少ないほど高いスコアが得られます。
実装の詳細
以下のプロシージャを実装してください。
long long play_game()- このプロシージャは、各テストケースに対して最大 $T$ 回呼び出されます。
- このプロシージャは、隠された数 $S$ を特定し、それを返す必要があります。その際、隠された数について質問するために以下のプロシージャを呼び出します。
bool ask(long long x)- $x$: Alice の質問を指定する数。
- $x$ の値は $1$ 以上 $10^{18}$ 以下でなければなりません。
- このプロシージャは、Bob の回答を表すブール値を返します。
play_gameの呼び出しごとに、このプロシージャは最大 $150$ 回まで呼び出すことができます。
グレーダーの挙動は適応的（adaptive）です。つまり、特定のテストでは $S$ と $K$ の値は play_game が呼び出される前に固定されていません。グレーダーの回答が矛盾しないような $(S, K)$ のペアが少なくとも1つ存在することが保証されています。
制約
- $1 \le T \le 1000$
- $1 \le S \le 10^{18}$
- $1 \le K \le 150$
小課題
あなたの解法が上記の実装詳細に従っていない場合、または play_game が返す値が一度でも正しくない場合、スコアは $0$ となります。
それ以外の場合、$C$ をすべての play_game の呼び出しを通じてあなたの解法が質問した最大回数とします。スコアは以下の表に従って計算されます。
| 条件 | スコア |
|---|---|
| $132 < C \le 150$ | $20 \cdot (\frac{150-C}{18})^2$ |
| $78 < C \le 132$ | $20 + 20 \cdot (\frac{132-C}{54})^2$ |
| $72 < C \le 78$ | $40 + 30 \cdot (\frac{78-C}{6})^2$ |
| $67 < C \le 72$ | $70 + 30 \cdot (\frac{72-C}{5})^2$ |
| $C \le 67$ | $100$ |
入出力例
隠された整数が $S = 2$、$K = 1$ であるシナリオを考えます。ゲームは以下の呼び出しで始まります。
play_game()play_game が最初に ask(2) を呼び出したとします。$2 \le S = 2$ であり、この時点では Bob は真実を話しているため、呼び出しは true を返します。
次に play_game が再度 ask(2) を呼び出したとします。$2 \le S = 2$ という条件は依然として成り立ちますが、Bob はすでに $K = 1$ 回真実を話しているため、現在は嘘をついており、呼び出しは false を返します。同じ質問に対して矛盾する回答を受け取ることで、Bob がそれ以降のすべての回答で嘘をつくことが判明します。
次に play_game が ask(3) を呼び出したとします。$3 \le S = 2$ は偽であり、Bob は嘘をついているため、呼び出しは true を返します。この時点で、$2 \le S < 3$ であることが推論でき、これは $S = 2$ を意味します。
したがって、このプロシージャは $2$ を返す必要があります。
サンプルグレーダー
サンプルグレーダーは適応的ではありません。$T$ 個のシナリオを処理し、各ケースにおいて入力から $S$ と $K$ の固定値を読み取り、それに応じて質問に回答します。
入力
T S[0] K[0] S[1] K[1] ... S[T-1] K[T-1]
ここで、$S[i]$ および $K[i]$ ($0 \le i < T$) は、各 play_game の呼び出しに対する隠されたパラメータを指定します。
出力
G[0] C[0] G[1] C[1] ... G[T-1] C[T-1]
ここで、$G[i]$ ($0 \le i < T$) は隠されたパラメータが $S[i]$ および $K[i]$ であるときに play_game が返した値であり、$C[i]$ はその呼び出し中に質問した回数です。