← 返回题目列表

Codeforces · 2196/C1

C1. 交互式图表(简单版)

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

这是问题的简单版本。版本之间的区别在于,在此版本中,您最多可以提出 $$$32 \cdot (n + m)$$$ 问题,以及 $$$n \leq 15$$$ 问题。只有解决了该问题的所有版本,您才能破解。

这是一个交互问题。

评审团想到了一个没有循环和多条边的有向无环图,它有 $$$n$$$ 个顶点和 $$$m$$$ 个边。

您的任务是确定该图中有哪些边。为此,您可以提出以下形式的问题:第 $$$k$$$ 条路径在图中所有路径的字典顺序 $$$^{\text{*}}$$$ 排序列表中是什么样子。

图中的路径是一系列顶点 $$$u_{1}, u_{2}, \dots, u_{l}$$$,这样对于任何 $$$i \lt l$$$,图中都存在一条边 ($$$u_{i}, u_{i + 1}$$$)。

你的任务是通过提出不超过 $$$32 \cdot (n + m)$$$ 的问题来完成此任务。

$$$^{\text{*}}$$$当且仅当满足以下条件之一时,序列 $$$a$$$ 按字典顺序小于序列 $$$b$$$:

  • $$$a$$$ 是 $$$b$$$ 的前缀,但 $$$a \ne b$$$;或
  • 在 $$$a$$$ 和 $$$b$$$ 不同的第一个位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10$$$)。测试用例的描述如下。

每个测试用例都包含一行,其中包含一个整数 $$$n$$$ ($$$1 \le n \le 15$$$) — 图中的顶点数。

评审团保证给定的图不包含循环或多重边。

请注意,$$$m$$$ 对您来说是未知的。

互动

每个测试用例的交互都从读取整数 $$$n$$$ 开始。

那么您最多可以提出 $$$32 \cdot (n + m)$$$ 问题。

要提出问题,请输出格式为“的字符串”? k"(不带引号)($$$1 \le k \le 2^{30}$$$)。在每个问题之后,读取一个整数 $$$q$$$ — 第 $$$k$$$ 条路径中的顶点数。如果 $$$q = 0$$$,则这样的路径不存在;否则,读取 $$$q$$$ 整数 — 组成该路径的顶点数路径。

可以证明,在给定的约束下,图中不同路径的数量不超过$$$2^{30}$$$。

要报告您的答案,请首先输出格式为“的字符串”!米",然后以格式 " 输出描述边缘的 $$$m$$$ 行u v”,表示从 $$$u$$$ 到 $$$v$$$ 有一条边。可以按任意顺序输出边。输出答案不算查询。

打印每个查询后,不要忘记输出行尾并刷新$$$^{\text{*}}$$$ 输出。否则,你会得到 超出空闲限制 判决。

如果在任何交互步骤中您读取 $$$-1$$$ 而不是有效数据,您的解决方案必须立即退出。这意味着您的解决方案将收到 错误答案 由于无效查询或任何其他错误。未能退出可能会导致任意判决,因为您的解决方案将继续从关闭的流中读取。

黑客:

对于 hack,请使用以下格式:

第一行应包含一个整数 $$$t$$$ ($$$1\leq t\leq 10$$$) — 测试用例的数量。

每种情况的第一行应包含两个整数 $$$n, m$$$ ($$$1 \leq n \leq 15$$$, $$$0 \leq m \leq \frac{n \cdot (n - 1)}{2}$$$) - 图中顶点和边的数量。

接下来的 $$$m$$$ 行应包含边缘的描述。每条边由两个整数 $$$v$$$、$$$u$$$ ($$$1 \leq v, u \leq n$$$, $$$v \neq u$$$) 定义,表示从顶点 $$$v$$$ 到顶点 $$$u$$$ 的一条边。

图形不能包含循环或多重边。

$$$^{\text{*}}$$$要刷新,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中;
  • sys.stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

示例

输入
复制

3
5

1 1

2 1 2

3 1 2 4

3 1 2 5

2 1 3

3 1 3 4

3 1 3 5

1 2

1 3

1 4

1 5

1

0

2

1 1

1 2

2 2 1

输出
复制


? 1

? 2

? 3

? 4

? 5

? 6

? 7

? 8

? 11

? 14

? 15

! 6
1 3
1 2
2 4
3 4
2 5
3 5

? 2

! 0

? 1

? 2

? 3

! 1
2 1

注意

第一个测试用例的图表。

在此图中,有 $$$15$$$ 路径,按字典顺序排列如下:

  • $$$1$$$
  • $$$1 \到 2$$$
  • $$$1 \到 2 \到 4$$$
  • $$$1 \到 2 \到 5$$$
  • $$$1 \到 3$$$
  • $$$1 \到 3 \到 4$$$
  • $$$1 \到 3 \到 5$$$
  • $$$2$$$
  • $$$2 \到 4$$$
  • $$$2 \ 到 5$$$
  • $$$3$$$
  • $$$3 \到 4$$$
  • $$$3 \到 5$$$
  • $$$4$$$
  • $$$5$$$