← 返回题目列表

Codeforces · 1158/E

E. 奇怪的设备

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

这是一个交互问题。

Vasya 喜欢解决测验。他发现了一个奇怪的装置,想知道它是如何工作的。

该设备使用具有 $$$n$$$ 个顶点的树(无环连接的无向图)进行加密,并使用从 $$$1$$$ 到 $$$n$$$ 的整数进行编号。要解决这个测验,您应该猜测这棵树。

幸运的是,该设备可以进行一次操作,使用该操作您应该猜测密码。您可以为设备提供一个非负整数数组 $$$d_1, d_2, \ldots, d_n$$$。在设备上,有$$$n$$$个灯,其中$$$i$$$与树的第$$$i$$$个顶点连接。对于所有 $$$i$$$,如果存在编号为 $$$j \neq i$$$ 且 $$$dist(i, j) \leq d_j$$$ 的树顶点,则灯将打开第 $$$i$$$ 个灯。让我们将 $$$dist(i, j)$$$ 定义为树中顶点 $$$i$$$ 和 $$$j$$$ 之间的距离,或者顶点 $$$i$$$ 和 $$$j$$$ 之间简单路径上的边数。

Vasya 想要使用设备进行 $$$\leq 80$$$ 运算来解决此测验并猜测树。帮助他!

互动

一开始,您的程序应读取一个整数 $$$n$$$ — 加密设备的树的顶点数 ($$$2 \leq n \leq 1000$$$)。

之后,您可以按以下格式进行多项操作。要执行操作,请打印一个符号“?” (不带引号)和 $$$n$$$ 整数 $$$d_1, d_2, \ldots, d_n$$$,后面用空格分隔。请注意,对于所有 $$$i$$$,您只能使用数字,满足不等式 $$$0 \leq d_i < n$$$。之后,您应该读取一个长度为 $$$n$$$ 的字符串 $$$s$$$,由符号“0”和“1”组成(不带引号)。对于所有 $$$i$$$,如果与树的第 $$$i$$$ 个顶点连接的设备上的灯关闭,则符号 $$$s_i$$$ 等于“0”,否则等于“1”。

经过几次操作后,您应该打印猜测的树。为此,请打印唯一的符号“!” (不带引号)。在接下来的 $$$n-1$$$ 行中,打印 $$$2$$$ 整数 $$$a_i$$$、$$$b_i$$$ - 由树的 $$$i$$$-th 边连接的顶点的索引。该数字应满足条件 $$$1 \leq a_i、b_i \leq n$$$ 和 $$$a_i \neq b_i$$$。这些边应该形成一棵树,相当于隐藏树。之后,您的程序应该终止。

可以保证,在每次测试中,树之前都是固定的,并且不会根据程序的操作而改变。

您的程序可以对设备进行从 $$$0$$$ 到 $$$80$$$ 的操作,然后猜测树与隐藏树相等。

如果您的程序将进行超过 $$$80$$$ 操作,它可以获得任何结论,因为它将继续从关闭的输入中读取。如果您的程序将以不正确的格式进行操作或打印答案,它也可以得到任何结论。当心。

打印问题和答案后不要忘记刷新输出。

要刷新输出,您可以使用:

- C++ 中的 fflush(stdout)。
- Java 中的 System.out.flush()。
- Python 中的 stdout.flush() 。
- 以帕斯卡格式刷新(输出)。
- 请参阅其他语言的文档。

黑客:

第一行应包含一个整数 $$$n$$$ — 树中的顶点数 ($$$2 \leq n \leq 1000$$$)。接下来的 $$$n-1$$$ 行应包含 $$$2$$$ 整数 $$$a_i$$$、$$$b_i$$$ - 由树的 $$$i$$$ 第一条边连接的顶点的索引 ($$$1 \leq a_i, b_i \leq n$$$, $$$a_i \neq b_i$$$)。所有边都应形成一棵树。请注意,不允许有额外的空格或换行符。

示例

输入 #1

5
00000
11011
11100
10010

输出 #1

? 0 0 0 0 0
? 1 1 2 0 2
? 0 0 0 1 0
? 0 1 0 0 1
!
4 2
1 5
3 4
4 1

注意

这是第一次测试中加密设备的树的图片:

这是该树中顶点之间的成对距离表:

- 如果您进行 $$$d = [0, 0, 0, 0, 0]$$$ 的操作,则不会有灯亮起,因为对于所有 $$$i \neq j$$$,$$$dist(i, j) > 0$$$。
- 如果执行 $$$d = [1, 1, 2, 0, 2]$$$ 的操作,则除了与 $$$3$$$-rd 顶点连接的灯之外的所有灯都会打开。例如,与 $$$1$$$-st 顶点连接的灯将打开,因为 $$$dist(1, 5) = 1 \leq 2 = d_5$$$。
- 如果执行 $$$d = [0, 0, 0, 1, 0]$$$ 的操作,则除了与第 $$$4$$$ 和第 $$$5$$$ 顶点连接的灯之外的所有灯都会打开。
- 如果您进行 $$$d = [0, 1, 0, 0, 1]$$$ 的操作,则只有与 $$$1$$$-st 和 $$$4$$$-th 顶点连接的灯才会打开。