CF1114E Arithmetic Progression

这是一个交互题！ 等差数列是指这样一个整数序列：每个元素与其前一个元素的差（$x_i - x_{i-1}$，其中 $i \ge 2$）是一个常数，这个常数称为该序列的公差。 也就是说，等差数列的形式为 $x_i = x_1 + (i - 1)d$，其中 $d$ 是该序列的公差。 现在有一个长度为 $n$ 的秘密整数列表 $a_1, a_2, \ldots, a_n$。 保证所有元素 $a_1, a_2, \ldots, a_n$ 都在 $0$ 到 $10^9$ 之间（包含端点）。 这个列表有一个特殊性质：将其升序排列后，会形成一个公差为正数（$d > 0$）的等差数列。例如，列表 $[14, 24, 9, 19]$ 满足这一要求，排序后为 $[9, 14, 19, 24]$，可以表示为 $x_n = 9 + 5 \cdot (n - 1)$。 你还拥有一个设备，但电量不足，因此你最多只能进行 $60$ 次如下两种类型的查询： - 给定一个值 $i$（$1 \le i \le n$），设备会显示 $a_i$ 的值。 - 给定一个值 $x$（$0 \le x \le 10^9$），设备会返回 $1$，如果存在严格大于 $x$ 的元素，否则返回 $0$。 你最多只能使用这台特殊设备进行 $60$ 次查询。你能否找出该等差数列的最小元素和公差？即，找出等差数列定义中的 $x_1$ 和 $d$。注意，数组 $a$ 并不是有序的。

交互开始时，首先输入一个整数 $n$（$2 \le n \le 10^6$），表示整数列表的长度。 接下来你可以进行以下两种类型的查询： - "? i"（$1 \le i \le n$）—— 获取 $a_i$ 的值。 - "> x"（$0 \le x \le 10^9$）—— 检查是否存在大于 $x$ 的元素。 每次查询后，读取其结果 $r$，为一个整数。 - 对于第一种查询，$r$ 满足 $0 \le r \le 10^9$。 - 对于第二种查询，$r$ 为 $0$ 或 $1$。 - 如果你进行了超过 $60$ 次查询，或查询的数值超出了范围，将会得到 $r = -1$。 - 如果你在收到 $-1$ 后终止，将会得到“Wrong answer”判定。否则你的程序会继续从已关闭的流中读取，可能得到任意判定。 当你确定了最小元素 $x_1$ 和公差 $d$ 后，输出 - "! $x_1$ $d$" 然后退出。该输出不计入 $60$ 次查询限制。 每次输出查询后，别忘了输出换行符并刷新输出缓冲区，否则会因“Idleness limit exceeded”而判错。具体做法如下： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其它语言请参考相关文档。 Hack 数据格式 Hack 时，使用如下格式： 第一行包含一个整数 $n$（$2 \le n \le 10^6$），表示列表长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^9$），表示列表中的元素。 同时，排序后的列表必须构成一个公差为正数的等差数列。

见上文输入格式说明。

请注意，示例交互中包含了额外的空行以便于阅读。实际交互中不会有任何空行，你也不应输出任何额外的空行。 示例测试中的列表为 $[14, 24, 9, 19]$。 由 ChatGPT 4.1 翻译