← 返回题目列表

Codeforces · 750/F

F. 新年与寻根

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

这是一个交互问题。在下面的交互部分中,您将找到有关刷新输出的信息。

高度为 h 的新年树是一棵完美二叉树,其顶点按某种顺序编号为 1 到 2h - 1。在这个问题中,我们假设 h 至少为 2。下图显示了一个高度为 3 的新年树示例:

北极熊喜欢装饰新年树,利马克也不例外。为了装饰树,他必须首先找到它的根,即恰好有两个邻居的顶点(假设 h ≥ 2)。这并不容易,因为利马克是一只小熊,他甚至看不到整棵树。你能帮助他吗?

有 t 个测试用例。在每个测试用例中,您应该首先从输入中读取 h 。然后,您最多可以提出 16 个问题,格式为“? x”(不带引号),其中 x 是 1 到 2h - 1 之间的整数(包含 1 和 2h - 1)。作为回复,您将获得顶点 x 的邻居列表(更多详细信息请参见下面的“交互”部分)。例如,对于上图中的一棵树,在询问“?1”后,您将得到 3 个邻居的响应:4、5 和 7。您的目标是找到根 y 的索引并以“! y”格式打印它。仅在打印前一个测试用例中的答案并刷新输出后,您才能读取下一个测试用例的 h 。

每棵树从一开始就是固定的,并且在您提出问题时不会改变。

输入

输入的第一行包含一个整数 t (1 ≤ t ≤ 500) — 测试用例的数量。

在每个测试用例的开头,您应该从输入中读取一个整数 h (2 ≤ h ≤ 7) - 树的高度。在回答上一个测试用例之前,您无法读取下一个测试用例中的 h 值。

互动

要询问有关顶点 x 的邻居的问题,请在单独的行上打印“? x”(不带引号)。请注意,您必须在该行的最后一个字符之后打印行结束字符并刷新输出以获得响应。

响应将由两行组成。第一行将包含一个整数 k (1 ≤ k ≤ 3)——顶点 x 的邻居数量。第二行将包含 k 个不同的整数 t1, ..., tk (1 ≤ t1 < ... < tk ≤ 2h - 1) - 顶点 x 的邻居索引,以升序给出。

在问最多 16 个问题后,您必须说 y — 根的索引。打印“!y”(不带引号)和行尾字符,并刷新输出。

每棵树从一开始就是固定的,并且在您提出问题时不会改变。

如果您不打印任何内容或忘记刷新输出,则可能会出现空闲限制超出。

要刷新,您可以使用(仅打印查询/答案和行尾):

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

在任何时刻,如果程序读取 h = 0 或 k = 0,它应该立即正常终止(例如,调用 exit(0))。这意味着系统检测到您的程序不正确的请求/输出并打印 0,因为如果无法再处理您的请求。在这种情况下,您将收到“错误答案”的判决,但如果您忽略 h = 0 或 k = 0 的情况,则可能会导致“运行时错误”、“超出时间/内存限制”或任何其他判决,因为您的程序可能会从关闭的输入流中读取垃圾。

黑客攻击。要破解某人,请使用以下格式:

第一行应包含一个等于 1 的整数 t(hacks 中只允许一个测试用例)。第二行应包含一个整数 h。接下来的 2h - 2 行中的每一行应包含两个不同的整数 ai 和 bi (1 ≤ ai, bi ≤ 2h - 1),表示通过边连接的两个节点。打印的边缘必须形成高度为 h 的完美二叉树。

当然,参赛者程序将无法看到此输入。

示例

输入 #1

1
3
3
4 5 7
2
1 2
1
2

输出 #1

? 1
? 5
? 6
! 5

输入 #2

2
2
1
3
2
1 2
2
1 2
4
3
3 12 13

输出 #2

? 1
? 3
? 3
! 3
? 6
! 1

注意

在第一个示例中,一棵树对应于语句中的绘图。

在第二个示例中,有两个测试用例。第一个测试用例中的树的高度为 2,因此有 3 个顶点。第二个测试用例中的树的高度为 4,因此有 15 个顶点。您可以在下图中看到两棵树。