题目详情题解（0）讨论（0）提交记录（0）

CFCF2196C1.Interactive Graph (Simple Version)

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

这是本题的简单版本。各版本的区别在于，本版本中你最多可以发起 32⋅(n+m)32 \cdot (n + m) 次询问，且 n≤15n \leq 15。只有当你解决了所有版本时，你才能进行 hack。

本题为交互题。

出题人想好了一个有向无环图（无自环且无重边），图包含 nn 个点和 mm 条边。

你的任务是通过发问，判断图中存在哪些边。你可以提出如下一类询问：在该图中，所有路径按字典序排序后，第 kk 条路径是怎样的？

图中的一条路径定义为一系列顶点 u1,u2,…,ulu_{1}, u_{2}, \dots, u_{l}，其中对于任意 i<li < l，图中存在一条从 uiu_i 到 ui+1u_{i+1} 的有向边 (ui,ui+1)(u_i, u_{i+1})。

你的总询问次数不得超过 32⋅(n+m)32 \cdot (n + m)。

∗^* 一个序列 aa 按字典序小于序列 bb，当且仅当满足以下条件之一：

  • aa 是 bb 的前缀，且 a≠ba \ne b；
  • 在 aa 和 bb 的第一个不同的位置，aa 该处的元素小于 bb 该处对应元素。

输入格式

每个测试点包含多组测试数据。第一行包含一个整数 tt（1≤t≤101 \le t \le 10），表示数据组数。

每组测试数据包含一行一个整数 nn（1≤n≤151 \le n \le 15），表示图的顶点数。

保证所给图无环且无重边。

注意：你并不知道 mm 的值。

输出格式

（交互题，无标准输出格式）

输入输出样例

  • 输入#1

    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

    ? 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

说明/提示

第一组测试数据的图如下所示。

对于该图，共有 1515 条路径，按字典序排序如下：

  • 11
  • 1→21 \to 2
  • 1→2→41 \to 2 \to 4
  • 1→2→51 \to 2 \to 5
  • 1→31 \to 3
  • 1→3→41 \to 3 \to 4
  • 1→3→51 \to 3 \to 5
  • 22
  • 2→42 \to 4
  • 2→52 \to 5
  • 33
  • 3→43 \to 4
  • 3→53 \to 5
  • 44
  • 55
首页