310309: CF1812H. Expected Twist
Description
This is an interactive problem.
There is an array $a_1, a_2, \dots, a_n$ of $n$ integers hidden from you. Your task is to find the smallest element of the array.
To do this, you can ask several queries. In each query, you can pick two integers $l$ and $r$ ($1 \leq l \leq r \leq n$). In return, you will be given the value of $\max(a_l, a_{l+1}, \dots, a_r)$. In other words, you will be told the maximum value of the subarray from $a_l$ to $a_r$.
Find the minimum of the array. You can ask at most $\mathbf{624}$ queries.
It is guaranteed that the values $a_1, a_2, \dots, a_n$ are chosen uniformly at random between $0$ and $2^{32}-1$ (inclusive).
InteractionBegin the interaction by reading an integer $n$ ($1 \le n \le 10^4$) on a separate line.
To ask a query, print a line in the form $\texttt{?}\;\;l\;\;r$ ($1 \le l \le r \le n$). Then you should read a single line containing the answer to your query.
After you have determined the answer, print a line in the form $\texttt{!}\;\;x$ where $x$ is the minimum value.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Answer $\texttt{-1}$ means that you made an invalid query. Exit immediately after receiving $\texttt{-1}$ and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.
ExampleInput3 1295320727 984617979 1295320727 167316954Output
? 1 3 ? 1 1 ? 2 2 ? 3 3 ! 167316954
Input
题意翻译
这是一道交互题。 有一个序列 $a_1,\dots,a_n$，每次你可以询问对于 $l,r$，$\max(a_l,a_{l+1},\dots,a_r)$ 的值，换言之，你将得到这个区间的最大值。 请求出这个序列的最小值。你至多可以询问 $\bf 624$ 次。 保证每个数字均为在 $0$ 和 $2^{31}-1$（含端点）间随机选择的。Output
这是一个交互式问题。有一个包含n个整数的数组\(a_1, a_2, \dots, a_n\)被隐藏起来，你的任务是找到数组中的最小元素。
为了做到这一点，你可以提出几个查询。在每次查询中，你可以选择两个整数\(l\)和\(r\) (\(1 \leq l \leq r \leq n\))。作为回应，你将得到\(\max(a_l, a_{l+1}, \dots, a_r)\)的值。换句话说，你将被告知从\(a_l\)到\(a_r\)的子数组的\textbf{最大}值。
找到数组的最小值。你最多可以提出\(\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\)是最小值。
在打印查询后，别忘了输出行尾并刷新输出。否则，你会得到\texttt{Idleness limit exceeded}。为此，请使用：
- 在C++中：\texttt{fflush(stdout)}或\texttt{cout.flush();}
- 在Java中：\texttt{System.out.flush();}
- 在Pascal中：\texttt{flush(output);}
- 在Python中：\texttt{stdout.flush();}
- 查看其他语言的文档。
答案\texttt{-1}表示你提出了一个无效查询。在收到\texttt{-1}后立即退出，你将看到\texttt{Wrong answer}的判决。否则，你可能会得到任意的判决，因为你的解决方案将继续从已关闭的流中读取。
输入输出数据格式：
输入：
- 第一行包含一个整数\(n\)，表示数组的长度。
- 之后的每一行包含对查询的响应，即子数组\([l, r]\)的最大值，直到你找到最小值。
输出：
- 查询格式为\texttt{?}\;l\;r\，用于查询子数组\([l, r]\)的最大值。
- 当你找到最小值时，输出格式为\texttt{!}\;x\，其中\(x\)是你找到的最小值。
注意：在实际的编程问题中，你不会被告知数组的具体内容，你需要通过查询来找出最小值。题目大意： 这是一个交互式问题。有一个包含n个整数的数组\(a_1, a_2, \dots, a_n\)被隐藏起来，你的任务是找到数组中的最小元素。 为了做到这一点，你可以提出几个查询。在每次查询中，你可以选择两个整数\(l\)和\(r\) (\(1 \leq l \leq r \leq n\))。作为回应，你将得到\(\max(a_l, a_{l+1}, \dots, a_r)\)的值。换句话说，你将被告知从\(a_l\)到\(a_r\)的子数组的\textbf{最大}值。 找到数组的最小值。你最多可以提出\(\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\)是最小值。 在打印查询后，别忘了输出行尾并刷新输出。否则，你会得到\texttt{Idleness limit exceeded}。为此，请使用： - 在C++中：\texttt{fflush(stdout)}或\texttt{cout.flush();} - 在Java中：\texttt{System.out.flush();} - 在Pascal中：\texttt{flush(output);} - 在Python中：\texttt{stdout.flush();} - 查看其他语言的文档。 答案\texttt{-1}表示你提出了一个无效查询。在收到\texttt{-1}后立即退出，你将看到\texttt{Wrong answer}的判决。否则，你可能会得到任意的判决，因为你的解决方案将继续从已关闭的流中读取。 输入输出数据格式： 输入： - 第一行包含一个整数\(n\)，表示数组的长度。 - 之后的每一行包含对查询的响应，即子数组\([l, r]\)的最大值，直到你找到最小值。 输出： - 查询格式为\texttt{?}\;l\;r\，用于查询子数组\([l, r]\)的最大值。 - 当你找到最小值时，输出格式为\texttt{!}\;x\，其中\(x\)是你找到的最小值。 注意：在实际的编程问题中，你不会被告知数组的具体内容，你需要通过查询来找出最小值。