单点时限: 1.0 sec
内存限制: 512 MB
Greatly inspired by his friend — Quber CC, who is a world-famous camper, Cuber QQ has recently started camping. Camping is a kind of enjoyment to experience nature, but admittedly, it is inevitable to encounter difficulties. In order to collect some information about the camping site, it is often necessary to ask for some help from talented guys.
The camping site can be represented by a matrix of $n\times n$. The rows and columns are both numbered from $0$ to $n - 1$ and the heights of each coordinate $h_{i, j}$ are pairwise different and $0 \leq h_{i, j} < 10^ 9$.
Cuber QQ want to you help him to find a coordinate that is \textbf{extremely high}. A coordinate is extremely high when it is higher than all of the surrounding coordinates. Note that the surrounding coordinates of $(x, y)$ are $(x - 1, y)$, $(x, y - 1)$, $(x + 1, y)$ and $(x, y + 1)$. If one or more of them is unavailable (e.g., $(x, y)$ lies on the border), the comparison can be skipped.
he input starts with a line containing integer $n$ ($3 \leq n \leq 500$) — the size of the camping site. Your program should read it at first.
After that your program should print to the standard output the requests about the height of any coordinate or inform that the “extremely high” coordinate is found.
? x y, ($0 \leq x, y \leq n - 1$).! x y, ($0 \leq x, y \leq n - 1$).The response on a request is an integer — the height of $(x, y)$, printed on a separate line.
You can assume that the height of the coordinates out of the bound is $-1$. If there are multiple eligible coordinates, just find any one.
Your program can do at most $8n$ requests. Note that the final line ! x y is not counted as a request.
Do not forget about flush operation after each printed line. To do this, use:
fflush(stdout) or cout.flush() in C++;System.out.flush() in Java;stdout.flush() in Python;After your program prints the extremely high coordinate, it should terminate normally.
0 1 2 3 4 5 6 7 8
? 0 0 ? 0 1 ? 0 2 ? 1 0 ? 1 1 ? 1 2 ? 2 0 ? 2 1 ? 2 2 ! 2 2
The complete matrix of the sample is shown as below:
0 1 2
3 4 5
6 7 8