26171번 - An Interactive Problem 다국어인터랙티브

Troubles in the jury! The contest day of NWERC is tomorrow already, and they still need a nice interactive problem for the problem set. During this test session, the jury have gathered in an emergency meeting and started discussing problem ideas. All of the $n^2$ jury members have an idea for an interactive problem, and even after hours of arguing, they cannot decide which idea is the nicest. To resolve the discussion as quickly as possible, they decide to draw lots.

Each member of the jury draws a lot from a collection of unique numbers. Because the number of jury members is square and they like regular shapes, they place all the lots face-down on a table, laid out in the shape of a square. They task you to be the independent lot-drawer, to see which jury member has drawn the highest number. To make sure you are truly independent, you are not allowed to see the table, hence you to pick the lots on the table by shouting coordinates. They are in a hurry, though, so you need to find the lot with the highest number in at most $n^2 + 100$ commands. You do not know the size of the square beforehand, but you do know that $n$ is at least $1$ and at most $100$.

This is an interactive problem. Your submission will be run against an interactor, which reads from the standard output of your submission and writes to the standard input of your submission. This interaction needs to follow a specific protocol:

Your program should make at most $n^2 + 100$ queries to find the lot with the highest value. Each query is made by printing one line of the form "? $x$ $y$" ($1\leq x, y\leq 1000$), the coordinate of the lot you want to uncover. Note that the top-left corner of the square of lots is always at $(1, 1)$. The interactor will respond with either an integer $v$ ($1 \leq v \leq 10^9$), indicating the value on the drawn lot, or the string "ArrayIndexOutOfBoundsException" if the chosen coordinate is outside the square.

When you have determined the lot with the highest value $v$, print one line of the form "! $v$", after which the interaction will stop. Printing the answer does not count as a query.

If there are multiple valid solutions, you may output any one of them.

Make sure you flush the buffer after each write.

A testing tool is provided to help you develop your solution.

Using more than $n^2 + 100$ queries will result in a wrong answer.

• 1.in
• testing_tool.py