← 返回题目列表

AtCoder · tkppc4_2_l

L. 建筑与女巫

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

配点:1300 点

该问题是一个交互式问题,因此格式与普通问题不同。请注意。

問題文

在帕肯王国, 有N 个城市。另外,N - 1 它们由连接双向的道路连接起来,您可以仅使用这些道路从任何城市前往任何城市。也就是说,帕肯王国形成了一个“树形结构”。
每个城市也有代表它的建筑物。 有 1 件。 第


现在,E869120,你想知道帕肯王国的结构,即帕肯王国的每条道路都连接到哪些城市,但是这并不容易知道,因为帕肯王国已经被恶魔封锁了。
因此,我试图通过向帕肯王国的总统女巫塞格特里询问以下问题来了解帕肯王国的结构。

  • 长度 小于或等于 N 的排列 给出了 p 。在这里,p 是 您也可以写 1 以上 N 以下值为 必须包含每个 1 。
  • 让赛格特里先生使用他的魔法力量创造一座城市。 i 代表性建筑物的高度为 2^{p_i - 1} 进行设置。
  • 并且, 当按0 以上 2^{N}-1 值小于或等于 指定 x 并满足以下条件 (u, v) (u < v) 对数 让他们回答 e 。 在到达
    • u 减去 v 的最短路径上,其经过的城市中建筑物的总高度为 x 类似的东西。


例如,当帕研王国具有如下图所示的结构时,p = {1, 5, 3, 4, 2}, x = 21 ,

  • 首先,各城市建筑的高度如下图所示,为 {1, 16, 4, 8, 2}。
  • 因此, 输出(u, v) = (1, 3), (1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5) 可以得到第 7 在街道上 x \geq 21 为满足 条件,魔女 Segtree 先生7 。
  • 例如,1 减去 5 到 的最短路径中经过的城市建筑高度总和为1 (都市 1) + 16 (都市 2) + 8 (都市 4) + 2 (都市 5) = 27 变为 通过21 以上,因此条件得以满足。


E869120 如果你向女巫 Segtree 先生提问过多,帕研王国的军队袭击的可能性会增加,因此希望尽可能用最少的提问次数了解帕研王国的结构。特别是,3 \ 600 如果超过 次提问,不仅军队,连 Segtree 先生也会大发雷霆,自动判定为错误。
但是对他来说这个问题太难了,解不了。请为他编写一个程序,用尽可能少的提问次数来猜测结构。

制約

  • 1 \leq N \leq 60
  • 帕研王国组成了一个连通的树结构。也就是说,可以从任意城市沿道路到达任意城市。

小課題

这道题有,2 个小题。
  1. (100 点) N \leq 4 很满意。
  2. (1200 点) 5 \leq N \leq 60 很满意。

然而,小任务 对于 2 在 中,得分取决于最多的提问次数。 Q 通过 的最大提问次数决定得分。

提问次数最大值 Q 小課題 2 的得分 (1 \ 200 点満点)
2 \ 001 \leq Q \leq 3 \ 600 310
1 \ 721 \leq Q \leq 2 \ 000 420
1 \ 101 \leq Q \leq 1 \ 720 550
601 \leq Q \leq 1 \ 100 1 \ 200 - (Q - 600)
Q \leq 600 1 \ 200

入出力

由于这个问题是交互式问题,因此与通常的输入输出格式不同,请注意。

(△) 首先,从评测器接收城市数量 N 以下格式。

N

接着,重复进行 (☆) 和 (★) 的输入输出,直到了解帕研王国的结构。

(☆) 自己向魔女(评测器)提出问题,格式如下。

? p_1 p_2 p_3 ... p_N x

首先,输出 '?' 然后输出 N + 1 个整数。输出时, ? 包括 在内全部在同一行输出。请参考题目说明获取p, x 的值。
另外,p 是 您也可以写 1 以上 N 以下的值 1 需要是包含 次的不同排列,并且x 是 您也可以写 0 以上 2^{N}-1 必须为以下值。 最后不要忘记换行。


(★) 魔女(评测器)会对问题做出回答。

回答表示为1 整数 e 。向评测器提问后,1 请接收 个整数。
但是, 运算前设定中包含的3 \ 600 超过 次提问时,-1 返回该值。在这种情况下,请立即结束程序。如果超过了问题限制次数而结束程序,则行为为 WA;但如果不结束程序,行为未定义。


(◇) 当您了解了答案所对应的帕研王国结构时,请按如下方式输出。

!
a_1 b_1
a_2 b_2
a_3 b_3
...
a_{N-1} b_{N-1}

这样,N 行。
但是, 运算前设定中包含的a_i, b_i 表示帕研王国的结构值。具体来说,i 第几条道路 a_i 和 按字典顺序比较 b_i 连接了什么,指的就是这个。
道路的输出顺序可以随意。此外,a_i, b_i 的顺序也可以相反。例如,当帕研王国的道路是 (1, 2), (2, 3), (3, 4) 时,即使像下面这样输出也可以算作正确。

3 2
1 2
4 3

注意

如果输出格式错误,评测行为不确定。(不一定是 WA。)
此外,输出最后必须执行 flush,否则可能会 TLE。
E869120 君3 \ 600 不能超过规定次数提出问题。如果超过此次数问题仍未中止程序,行为未定义。
请注意,即使 AC,也可能没有取得满分。小课题 1, 2 在所有测试用例中 3 \ 600 如果能在规定次数内得到答案,即使只得到部分得分,也会显示 AC。

入出力例 1

这个输入例子是N = 4 是一个针对帕研王国在以下结构时与评测方交互的示例。

程序的输入(判断端输出) 我的程序的输出
4
? 1 2 3 4 8
3
? 4 3 2 1 15
1
! 
1 2
2 4
1 3

作者: E869120