← 返回题目列表

Codeforces · 2155/D

D. 电池

中文机器翻译题面 查看原题

这是一个交互问题。请参阅下面的交互部分以获得更好的理解。

有 $$$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$$$ 是否打开手电筒。陪审团回应说他们愿意。找到一对可以工作的电池,因此第一个测试用例的交互成功终止。

请注意,示例输入和输出中的换行符是为了清楚起见,在实际交互中不会出现。