无聊的游戏 - 問題

Alice 和她的弟弟 Bob 正在玩一个猜数字游戏。

Bob 选择了一个（隐藏的）整数 $S$。

Alice 可以询问关于这个隐藏数字的问题，形式如下：“隐藏数字至少是 $x$ 吗？” Bob 用“是”或“否”来回答她的问题。不幸的是，在 $K \ge 1$ 次提问后，Bob 对游戏感到厌倦，从那时起，他会对所有问题给出错误的回答。

也就是说，Bob： 对于前 $K$ 次提问，当且仅当 $x \le S$ 时回答“是”。 在第 $K$ 次提问之后，当且仅当 $S < x$ 时回答“是”。

注意，Bob 对第一个问题总是回答正确，且 Alice 不知道 $K$ 的值。

你的任务是设计并实现一种提问策略，让 Alice 能够确定这个隐藏数字。你的得分取决于提问的次数——提问次数越少，得分越高。

你需要实现以下过程：

long long play_game()

该过程应通过调用以下过程来询问关于隐藏数字的问题，从而找到并返回隐藏数字 $S$：

bool ask(long long x)

评测器的行为是自适应的，这意味着在某些测试中，$S$ 和 $K$ 的值在调用 play_game 之前并未固定。保证至少存在一对 $(S, K)$，使得评测器的回答是一致的。

如果你的解法不符合上述实现细节，或者即使在单次调用中 play_game 返回的值不正确，你的得分将为 $0$。

否则，令 $C$ 为你的解法在所有 play_game 调用中提问次数的最大值。你的得分根据下表计算：

考虑隐藏整数 $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]$ 是该次调用期间提问的次数。

QOJ.ac