P6716 [CCO 2018] Gradient Descent

**This is an interactive problem.**

Troy wants to play a game with you. The game uses an $R \times C$ grid. There are $N$ pieces (numbered from $1$ to $N$). The $i$-th piece is placed at $(X_i, Y_i)$. **Multiple pieces may be on the same cell.** In one second, Troy can move one piece to a vertically or horizontally adjacent cell. Troy defines the score of a cell as the minimum number of seconds needed to move all $N$ pieces to that cell. Your task is to find the minimum score among all cells on the board. Troy will not tell you the value of $N$ or the positions of the pieces, but you may ask Troy at most $K$ questions: the score of cell $(p, q)$. #### Interactive Strategy **This is an interactive problem.** First, read three integers $R, C, K$, representing the size of the grid and the maximum number of questions you may ask. After reading this line, your program may ask questions about the score of $(p, q)$ (in the format `? p q`), and then you will receive an integer $s$ representing the score of that cell. Once your program determines the minimum score among all cells on the board, it should output `! Z` and terminate, where $Z$ is the final answer. After outputting each line, you must flush the buffer: - C/C++: `fflush(stdout)` or `cout

None

None

#### Sample Explanation For sample $1$ |Request|Response| |:-:|:-:| ||`1 10 90`| |`? 1 3`|`9`| |`? 1 7`|`11`| |`? 1 4`|`8`| |`! 8`|| The piece positions should be $(1,2)$, $(1,4)$, and $(1,10)$, so the minimum score over the whole board is $8$ (the score of cell $(1,4)$). For sample $2$ |Request|Response| |:-:|:-:| ||`5 4 170`| |`? 2 4`|`11`| |`? 1 4`|`15`| |`? 3 3`|`7`| |`! 7`|| The piece positions should be $(2,3)$, $(2,3)$, $(4,3)$, $(5,1)$. #### Constraints For $100\%$ of the testdata, $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$。 For $20\%$ of the testdata, $R = 1$, $C \le 90$, $K = 90$。 For another $20\%$ of the testdata, $R = 1$, $K = 90$。 For another $20\%$ of the testdata, $K = 170$。 For another $20\%$ of the testdata, $K = 100$。 For another $20\%$ of the testdata, $K = 75$。 The spj and interactive library are included in the attached files. #### Notes Translated from [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 author: @[FZzzz](https://www.luogu.com.cn/user/174045)。 Translated by ChatGPT 5