CF2155D Batteries

这是一个交互式问题。为便于理解，请参见下方的交互说明。 有 $n$ 节电池，编号为 $1, 2, \ldots, n$。其中有一些电池是工作的，另外一些不工作。设 $a$ 为工作的电池的数量。已知 $\mathbf{a \geq 2}$。 你知道 $n$ 的值，但不知道 $a$。 有一个手电筒，能同时装入两节电池，且只有当两节电池都工作时手电筒才会亮。这些电池已经被打乱，你不知道哪些电池是工作的，哪些是不工作的。你可以选择任意两节电池，并放入手电筒进行测试。 你的目标是找到一对都工作的电池。然而，你担心损坏手电筒，所以你希望尽量减少测试的次数。 因此，你需要在最多 $ \left \lfloor \frac{n^2}{a} \right \rfloor $ 次尝试内，找到一对都工作的电池。 评测器是自适应的。这意味着电池 $i$（$1 \le i \le n$）是否工作不是预先确定的，并且可能会在交互过程中发生变化。但保证始终存在一种含有 $a$ 节工作的电池的分布方式，和你至今得到的信息相一致。

每个测试包含多组测试用例。第一行为测试用例的数量 $t$（$1 \le t \le 50$）。每个测试用例的描述如下。 每个测试用例第一行为一个整数 $n$（$2 \le n \le 40$）——电池的数量。 保证所有测试用例中 $n$ 的总和不超过 $200$。

无

在第一个测试中，有 $3$ 节电池。只有第 $2$ 和第 $3$ 节电池是工作的。因此 $a=2$，我们需要在 $\lfloor \frac{3^2}{2} \rfloor = 4$ 次测试中找到一对都工作的电池。 交互过程如下： | 参与者 | 评测器 | 解释 | |:-----:|:------:|:----:| | — | $3$ | 这组数据有 $3$ 节电池 | | $1,2$ | $0$ | 你询问第 $1$ 与第 $2$ 节电池能否点亮手电筒。评测器回答不能。 | | $2,3$ | $1$ | 你询问第 $2$ 与第 $3$ 节电池能否点亮手电筒。评测器回答可以。这样就找到了两个都工作的电池，本组用例交互结束。| 在第二组测试用例中，有 $10$ 节电池。只有第 $1$、$4$、$6$、$9$ 节电池是工作的。因此 $a=4$，需要在 $\lfloor \frac{10^2}{4} \rfloor = 25$ 次测试中找到一对都工作的电池。 交互过程如下： | 参与者 | 评测器 | 解释 | |:-----:|:------:|:----:| | — | $10$ | 这组数据有 $10$ 节电池。 | | $1,2$ | $0$ | 你询问第 $1$ 和第 $2$ 节电池能否点亮手电筒。评测器回答不能。 | | $1,3$ | $0$ | 你询问第 $1$ 和第 $3$ 节电池能否点亮手电筒。评测器回答不能。 | | $1,4$ | $1$ | 你询问第 $1$ 和第 $4$ 节电池能否点亮手电筒。评测器回答可以。这样就找到了两个都工作的电池，本组用例交互结束。| 请注意，样例输入输出中的换行仅为清晰展示，实际交互过程中不会出现。 由 ChatGPT 5 翻译