← 返回题目列表

Codeforces · 1479/A

A. 搜索局部最小值

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

这是一个交互问题。

Homer 非常喜欢数组,他想和你玩一个游戏。

Homer 向您隐藏了整数 $$$1$$$ 到 $$$n$$$ 的排列 $$$a_1, a_2, \dots, a_n$$$。系统会要求您查找任意索引 $$$k$$$ ($$$1 \leq k \leq n$$$),该索引是局部最小值。

对于数组 $$$a_1, a_2, \dots, a_n$$$,如果 $$$a_i < \min\{a_{i-1},a_{i+1}\}$$$,则索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 被称为局部最小值,其中 $$$a_0 = a_{n+1} = +\infty$$$。如果一个数组包含从 $$$1$$$ 到 $$$n$$$ 的所有整数恰好一次,则该数组被称为整数 $$$1$$$ 到 $$$n$$$ 的排列。

最初,您只会获得 $$$n$$$ 的值,而不会获得有关此排列的任何其他信息。

在每个交互步骤中,您可以选择任何 $$$i$$$ ($$$1 \leq i \leq n$$$) 并用它进行查询。作为响应,您将获得 $$$a_i$$$ 的值。

要求您在最多 $$$100$$$ 查询后查找任何索引 $$$k$$$,该索引是局部最小值。

互动

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

要对索引 $$$i$$$ ($$$1 \leq i \leq n$$$) 进行查询,您应该在单独的行中输出“? $$$i$$$”。然后在单独的行中读取 $$$a_i$$$ 的值。 “?”的数量查询限制在 $$$100$$$ 以内。

当您找到局部最小值索引 $$$k$$$ ($$$1 \leq k \leq n$$$) 时,在单独的行中输出“! $$$k$$$”并终止程序。

如果您的查询格式无效,或者您输入的“?”超过 $$$100$$$查询,您将收到错误答案判决。

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

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

黑客格式

hack 的第一行应该包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$)。

第二行应包含 $$$n$$$ 不同的整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$)。

示例

输入 #1

5
3
2
1
4
5

输出 #1

? 1
? 2
? 3
? 4
? 5
! 3

注意

在示例中,第一行包含一个整数$$$5$$$,表示数组的长度为$$$n = 5$$$。

该示例创建了五个“?”查询,之后我们得出结论,数组 $$$a = [3,2,1,4,5]$$$ 且 $$$k = 3$$$ 是局部最小值。