AT_nupc2024_k A Shortcut

本题是一个**交互式**问题（你的程序将与评测程序通过输入输出进行交互）。 给定一个整数 $N$，评测机会隐藏一个由 $N$ 个顶点组成的无向图 $G$，其结构如下： - $G$ 的每个顶点编号为 $1$ 到 $N$。 - 对于所有满足 $1 \le i < N$ 的整数 $i$，顶点 $i$ 和顶点 $i+1$ 之间有一条边。 - 存在**唯一一组**满足 $y - x > 1$ 且 $1 \le x, y \le N$ 的整数对 $(x, y)$，使得顶点 $x$ 和顶点 $y$ 之间存在一条边。 - 除上述 $N$ 条边外，不存在其他边。 你可以对 $G$ 进行如下操作来查询信息： - 任选两个顶点编号 $p, q$，询问从顶点 $p$ 到顶点 $q$ 的最短路径（即经过的边的条数）。 请你在不超过 $\lceil \log_2 N + 1 \rceil$ 次查询之内，确定出 $(x, y)$。 评测机会提供 $T$ 组测试数据，请你对每一组测试数据都找出 $(x, y)$。

首先，标准输入会给出一个整数 $T$。 > $T$ 接着，有 $T$ 组测试数据。每组测试数据格式如下： 首先，输入一个整数 $N$。 > $N$ 然后，在每组数据中，你最多可以进行 $\lceil \log_2 N + 1 \rceil$ 次查询。 每次查询请输出如下格式到标准输出，其中 $p, q$ 满足 $1 \leq p, q \leq N$： > ? $p$ $q$ 每个查询后，会从标准输入获得一个响应，格式如下： > $\mathrm{dist}(p, q)$ 其中 $\mathrm{dist}(p, q)$ 表示从顶点 $p$ 到顶点 $q$ 的最短路径长度。如果你的查询不合法，或查询次数超过 $\lceil \log_2 N + 1 \rceil$ 次，评测机会输出 $-1$。 评测机输出 $-1$ 时，无论剩余测试数据如何，你的解答均被判为不正确，请立即退出程序。 确定 $(x, y)$ 后，请按如下格式输出，这不计入查询次数： > ! $x$ $y$ 随后若有下一组测试数据，请继续解答。所有测试数据回答完毕后，请终止程序。

无

### 注意事项 - 每次输出后请务必输出换行并刷新标准输出，否则可能会因为 TLE 被判失败。 - 评测机对非法输出和非法操作的判定可能不确定，请谨慎处理输入输出。 - $(x, y)$ 在你进行交互之前已经被固定，交互过程中不会变化。 ### 输入输出样例 | 输入 | 输出 | 说明 | |------|------|------| | 2 | | 首先输入一个整数 $T$。 | | 10 | | 第一组测试数据，首先输入一个整数 $N$。| | ? 1 10 | | 查询 $p = 1, q = 10$。 | | 6 | | 得到 $\mathrm{dist}(1, 10)=6$。 | | ? 8 6 | | 查询 $p = 8, q = 6$。 | | 2 | | 得到 $\mathrm{dist}(8, 6)=2$。 | | ? 3 7 | | 查询 $p = 3, q = 7$。 | | 1 | | 得到 $\mathrm{dist}(3, 7)=1$。 | | ! 3 7 | | 输出 $(x, y) = (3, 7)$ 作为答案。可以通过。 | | 3 | | 第二组测试数据，首先输入一个整数 $N$。| | ? 1 2 | | 查询 $p = 1, q = 2$。 | | 1 | | 得到 $\mathrm{dist}(1, 2)=1$。 | | ! 1 3 | | 输出 $(x, y) = (1, 3)$ 作为答案。可以通过。所有测试用例解答完毕，程序应终止。| ### 数据范围 - $1 \leq T \leq 10^3$ - $3 \leq N \leq 10^9$ - $1 \le x < y \le N$ - $y - x > 1$ - $T, N, x, y$ 均为整数 由 ChatGPT 5 翻译