Score : $500$ points

问题描述

这是一项互动任务（您的程序通过输入和输出与裁判程序进行交互）。

我们有一个 $N$×$N$ 的棋盘和 $N$ 个车。以下面的方式表示棋盘上从上到下第 $i$ 行、从左到右第 $j$ 列的格子：$(i, j)$。

考虑在棋盘的格子上放置车。您必须放置车，确保满足以下所有条件：

• 没有行包含两个或更多的车。
• 没有列包含两个或更多的车。

现在，已经有 $N-1$ 个车按照上述条件被放置在棋盘上。您需要选择一个没有被车占据的格子，并在该格子上放置一个车。（可以证明，在这些条件下至少存在一个可放置车的格子。）

但是，您不能直接看到棋盘上哪些格子被车占据了。

• 您可以选择整数 $A$、$B$、$C$ 和 $D$，使得 $1 \leq A \leq B \leq N$ 且 $1 \leq C \leq D \leq N$，然后询问在由格子 $(i, j)$ 形成的矩形区域内车的数量，其中满足 $A \leq i \leq B$ 且 $C \leq j \leq D$。

使用这种方式最多提问不超过 $20$ 次，找到并确定一个放置车的格子。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

This is an interactive task (where your program interacts with the judge's program via input and output).

We have an $N$-by-$N$ chessboard and $N$ rooks. Below, the square at the $i$-th row from the top and $j$-th column from the left is denoted by $(i, j)$.
Consider placing the rooks on squares of the chessboard. Here, you have to place the rooks so that all of the following conditions are satisfied.

• No row contains two or more rooks.
• No column contains two or more rooks.

Now, $N-1$ rooks are placed on the chessboard so that all of the above conditions are satisfied. You will choose a square that is not occupied by a rook and place a rook on that square. (It can be proved that there is at least one square on which a rook can be placed under the conditions.)

However, you cannot directly see which squares of the chessboard are occupied by a rook.
Instead, you may ask at most $20$ questions to the judge in the following manner.

• You choose integers $A$, $B$, $C$, and $D$ such that $1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N$, and ask the number of rooks in the rectangular region formed by the squares $(i, j)$ such that $A \leq i \leq B, C \leq j \leq D$.

Find a square to place a rook.

Constraints

• $2 \leq N \leq 10^3$
• $N$ is an integer.

Input and Output

This is an interactive task (where your program interacts with the judge's program via input and output).

First, receive the size of the chessboard, $N$, from Standard Input.

$N$

Next, repeat asking a question until you find a square to place a rook.

A question should be printed to Standard Output in the following format:

$?$ $A$ $B$ $C$ $D$

The response will be given from Standard Input in the following format:

$T$

Here, $T$ is the response to the question, or -1 if the question is invalid or more than $20$ questions have been asked.

When the judge returns -1, the submission is already regarded as incorrect. In this case, terminate the program immediately.

When you find a square to place a rook, let $(X, Y)$ be that square and print an answer in the following format. Then, terminate the program immediately.

$!$ $X$ $Y$

If there are multiple appropriate answers, any of them will be accepted.

Notes

• Each time you print something, end it with a newline and then flush Standard Output. Otherwise, you may get a TLE verdict.
• If an invalid output is printed during the interaction, the verdict will be indeterminate.
• Terminate the program immediately after printing an answer. Otherwise, the verdict will be indeterminate.

Sample Interaction

Below is an interaction where $N=3$ and the rooks are placed on $(1, 2)$ and $(2, 1)$.

Input	Output	Description
3		Judge first gives the integer $N$.
	? 1 2 1 3	Participant asks a question with $(A,B,C,D)=(1,2,1,3)$.
2		Judge returns the answer to the question, which is $2$.
	? 2 3 1 1	Participant asks a question with $(A,B,C,D)=(2,3,1,1)$.
1		Judge returns the answer to the question, which is $1$.
	? 1 3 3 3	Participant asks a question with $(A,B,C,D)=(1,3,3,3)$.
0		Judge returns the answer to the question, which is $0$.
	! 3 3	Participant finds the answer to be $(3, 3)$ and prints it.

update @ 2024/3/10 11:21:43