这是一个交互问题。
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 顶点连接的灯才会打开。