P6716 [CCO 2018] Gradient Descent

**本题为交互题。**

Troy 要和您一起玩游戏，他的游戏要用一个 $R \times C$ 的棋盘。 现在给定 $N$ 个棋子（从 $1$ 编号到 $N$），第 $i$ 个棋子放置在 $(X_i,Y_i)$ 处，**同一格可能有多个棋子**。 Troy 可以在一秒内将一个棋子移动到与其垂直或水平相邻的格子中，格子的分数就被 Troy 定义为将这 $N$ 个棋子挪到这个格子的秒数的最小值，您要做的就是找棋盘中格子里的分数的最小值。 Troy 不会告诉您 $N$ 的值和每个棋子的位置，但是您可以问 Troy 最多 $K$ 个问题：格子 $(p,q)$ 的分数。 #### 交互策略 **本题为交互题。** 首先，读入三个整数 $R,C,K$ 代表整个棋盘的大小，和您最多能问多少个问题。 读入完这一行后，您的程序将会对提出关于 $(p,q)$ 的分数的问题（格式为 `? p q`），然后您就会得到一个整数 $s$ 带包这个格子的分数。 一旦您的程序确定了棋盘中的格子的分数的最小值，那么就会输出 `! Z` 并终止程序，$Z$ 就代表最终结果。 在输出每一行后，都应刷新缓冲区： - C/C++：`fflush(stdout)` or `cout

None

None

#### 样例说明 对于样例 $1$ |请求|回答| |:-:|:-:| ||`1 10 90`| |`? 1 3`|`9`| |`? 1 7`|`11`| |`? 1 4`|`8`| |`! 8`|| 棋子的位置应该在 $(1,2)$，$(1,4)$ 和 $(1,10)$，所以我们得到的所有棋盘上的分数的最小值为 $8$（格子 $(1,4)$ 的分数）。 对于样例 $2$ |请求|回答| |:-:|:-:| ||`5 4 170`| |`? 2 4`|`11`| |`? 1 4`|`15`| |`? 3 3`|`7`| |`! 7`|| 棋子的位置应该在 $(2,3)$，$(2,3)$，$(4,3)$，$(5,1)$。 #### 数据规模与约定 对于 $100\%$ 的数据，$1 \le R,C \le 10^7$，$1 \le K \le 170$，$1 \le p\le R$，$1 \le q \le C$，$0 \le s \le 2 \times 10^9$，$1 \le N \le 100$，$1 \le X_i \le R$，$1 \le Y_i \le C$。 对于 $20\%$ 的数据，$R=1$，$C \le 90$，$K=90$。 对于另外 $20\%$ 的数据，$R=1$，$K=90$。 对于另外 $20\%$ 的数据，$K = 170$。 对于另外 $20\%$ 的数据，$K = 100$。 对于另外 $20\%$ 的数据，$K=75$。 spj 和交互库见附加文件。 #### 说明 翻译自 [Canadian Computing Olympiad 2018](https://cemc.math.uwaterloo.ca/contests/computing/2018/) Day 2 [A Gradient Descent](https://cemc.math.uwaterloo.ca/contests/computing/2018/stage%202/day2.pdf)。 spj 作者：@[FZzzz](https://www.luogu.com.cn/user/174045)。