这是一个交互问题。请参阅下面的交互部分以获得更好的理解。
有 $$$n$$$ ($$$2 \le n \le 40$$$) 电池,编号为 $$$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$$$。
互动
每个测试用例的交互都从读取整数 $$$n$$$ 开始。
要进行查询,请按以下格式打印包含两个整数的单行:
- $$$\mathbb{u}\,\mathbb{v}$$$ ($$$1 \leq u, v \leq n$$$ 和 $$$u \neq v$$$) — 您要测试的电池的索引。
之后,读取单个整数 $$$x$$$ — 指示插入 $$$2$$$ 电池后手电筒是否打开。如果$$$x=1$$$,则手电筒打开。否则,如果$$$x=0$$$,则手电筒没有打开。
找到一对可以打开手电筒的电池后,测试用例的交互被认为成功,并且将终止。之后,继续与下一个测试用例进行交互。
打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。
如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。
黑客
对于此问题,黑客已被禁用。
$$$^{\text{*}}$$$要刷新,请使用:
- fflush(标准输出) or cout.flush() 在 C++ 中;
- sys.stdout.flush() 在 Python 中;
- 请参阅其他语言的文档。
示例
输入复制
2 3 0 1 10 0 0 1
输出复制
1 2 2 3 1 2 1 3 1 4
注意
在第一次测试中,有 $$$3$$$ 电池。只有电池 $$$2$$$ 和 $$$3$$$ 可以工作。因此,$$$a=2$$$,我们必须找到一对可以在 $$$\lfloor \frac{n^2}{a} \rfloor = \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{n^2}{a} \rfloor = \lfloor \frac{10^2}{4} \rfloor = 25$$$ 查询中工作的电池。
交互过程如下:
| 参与者 | 评审团 | 说明 |
| — | $$$10$$$ | 此测试箱中有 $$$10$$$ 电池。 |
| $$$1$$$ $$$2$$$ | $$$0$$$ | 该解决方案询问电池 $$$1$$$ 和 $$$2$$$ 是否打开手电筒。陪审团回答说他们没有。 |
| $$$1$$$ $$$3$$$ | $$$0$$$ | 该解决方案询问电池 $$$1$$$ 和 $$$3$$$ 是否打开手电筒。陪审团回答说他们没有。 |
| $$$1$$$ $$$4$$$ | $$$1$$$ | 该解决方案询问电池 $$$1$$$ 和 $$$4$$$ 是否打开手电筒。陪审团回应说他们愿意。找到一对可以工作的电池,因此第一个测试用例的交互成功终止。 |
请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。