← 返回题目列表

AtCoder · nupc2024_k

K. 快捷方式

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

配点 : 100 点

問題文

这个问题是 互动 问题(您创建的程序和判断程序通过输入和输出交互的问题)。 给出了

整数 N 。另外,评委配置如下: N 顶点无向图 创建 G 已隐藏。

  • G 的每个顶点都有 它的编号为 1, 2, \dots , N 。 满足
  • 全部 1 \le i < N 的整数 选择 i ,顶点 i 与 边 i+1 之间有一条边。 满足
  • y - x > 1 和 1 \le x, y \le N 的整数集合 查找 (x, y) 是 在 就一个 存在和顶点 x 与 边 y 之间有一条边。 满足
  • 以上 N 除书本边缘外没有其他边缘。

你是 您必须在 G 发送以下查询。

  • 2 顶点数 选择 p, q 。顶点 询问 p 到顶点 q 的最短路径长度(路径上的边数)。 在

\lceil \log_2 N + 1 \rceil 查询中 请识别 (x, y) 。

注意,该判断不是自适应的,而是针对每个测试用例固定的。 我有 (x, y) 。 来自

测试用例是 给出了 T ,因此对于每个 (x, y) 。

制約

  • 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 是一个整数

入出力

首先,标准输入上的整数 T 。 对于

T

接下来, T 测试用例。每个测试用例均按以下格式给出:

首先是一个整数 最多可查询 N 。 对于

N

接下来, \lceil \log_2 N +1 \rceil 次。
请按以下格式将每个查询输出到标准输出。在这里, 必须是满足p, q 是 您也可以写 1 \le p, q \le 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 1 第二个测试用例已开始。在每个测试用例中,我们从一个整数开始 提出问题 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 2 第二个测试用例已开始。首先是一个整数 输出 N 。 对于
? 1 2 p = 1, q = 2 。
1 \mathrm{dist}(1, 2)=1 。 对于
! 1 3 作为答案 输出 (x, y) = (1, 3) 。这个输出是正确的。由于测试用例已完成,因此终止程序。