25768번 - Battleship: New Rules 다국어인터랙티브

문제

This is an interactive problem.

Ivan came up with new rules for the battleship game!

• The game will be played on an $n \times n$ board.
• The first player chooses an integer $k$ ($n \leq k \leq {\left\lceil \frac{n}{2} \right\rceil}^2$).
• After that, the first player places $k$ ships on the board so that the number of cells occupied by the ships is the maximum possible (among all valid placements of $k$ ships of any sizes).
• Each ship should be a rectangle of size 1ドル \times a$ or $a \times 1$ ($a$ is any integer from 1ドル$ to $n$ inclusive). Any two ships should not have neighbouring cells (by side or by corner).

After that, the second player starts his game.

• The second player knows only the size of the board $n$.
• The second player can ask a query: is cell $(x, y)$ occupied by some ship?
• The second player should find any empty 2ドル \times 2$ square on the board, or say that there are no such squares.

The second player can ask at most 6ドルn$ queries. Please play as the second player and win the game!

입력

출력

제한

인터랙션

The first line contains a single integer $t$ (1ドル \leq t \leq 100$) --- the number of games to be played. You should play $t$ games and finish interaction after that.

At the start of the game, you are given a single integer $n$ (3ドル \leq n \leq 1000$) --- the size of the board.

After that, you can ask some queries. To ask a query, print a single line "? $x$ $y$" (1ドル \leq x, y \leq n$) --- the coordinates of the cell. You will be given an answer $c$:

• If $c = -1,ドル you made too many queries. You should terminate your program.
• If $c = 0,ドル the cell $(x, y)$ is empty.
• If $c = 1,ドル the cell $(x, y)$ is occupied by some ship.

To finish the game, print a single line "! $x$ $y$", where:

• $x=-1,ドル $y=-1$ if there are no empty 2ドル \times 2$ squares on the board.
• Otherwise, 1ドル \leq x, y \leq n - 1$ and the square with cells $(x, y),ドル $(x+1, y),ドル $(x, y+1),ドル $(x+1, y+1)$ is empty.

If your answer is incorrect, you will be given a line with value -1, and you should terminate your program. Otherwise, you will be given a line with value 1, and you should play the next game (or finish your program if it was the last game).

It is guaranteed that the sum of $n$ for all games does not exceed 5000ドル$.

It is guaranteed that the board in each game is fixed, and the interactor is not adaptive.

Your solution will get Time Limit Exceeded if you don't print anything or forget to flush the output.

힌트

Boards from the first test are shown on pictures below. Rows correspond to $x$ coordinates, columns correspond to $y$ coordinates.