← 返回题目列表

Codeforces · 1812/H

H. 预期的扭曲

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

这是一个交互问题。

有一个数组 $$$a_1, a_2, \dots, a_n$$$ 个 $$$n$$$ 整数对你隐藏。你的任务是找到数组的最小元素。

为此,您可以询问几个问题。在每个查询中,您可以选择两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \leq l \leq r \leq n$$$)。作为回报,您将获得 $$$\max(a_l, a_{l+1}, \dots, a_r)$$$ 的值。换句话说,您将被告知从 $$$a_l$$$ 到 $$$a_r$$$ 的子数组的最大值。

找到数组的最小值。您最多可以提出 $$$\mathbf{624}$$$ 查询。

保证 $$$a_1, a_2, \dots, a_n$$$ 值在 $$$0$$$ 和 $$$2^{32}-1$$$(含)之间均匀随机选择。

互动

通过读取单独一行上的整数 $$$n$$$ ($$$1 \le n \le 10^4$$$) 开始交互。

要提出查询,请以 $$$\texttt{?}\;\;l\;\;r$$$ ($$$1 \le l \le r \le n$$$) 的形式打印一行。然后您应该阅读包含查询答案的一行。

确定答案后,以 $$$\texttt{!}\;\;x$$$ 的形式打印一行,其中 $$$x$$$ 是最小值。

打印查询后,不要忘记输出行尾并刷新输出。否则,您将超出空闲限制。为此,请使用:

- C++ 中的 fflush(stdout) 或 cout.flush();
- Java 中的 System.out.flush();
- 帕斯卡刷新(输出);
- Python 中的 stdout.flush() ;
- 请参阅其他语言的文档。

回答 $$$\texttt{-1}$$$ 表示您进行了无效查询。收到$$$\texttt{-1}$$$后立即退出,您将看到错误的答案判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

示例

输入 #1

3

1295320727

984617979

1295320727

167316954

输出 #1

? 1 3

? 1 1

? 2 2

? 3 3

! 167316954