102694: [AtCoder]ABC269 E - Last Rook
Description
Score : $500$ points
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
Input
题意翻译
**这是一道交互题。** 现在有一个 $n \times n$ 的国际象棋棋盘，左上角为 $(1,1)$，右下角为 $(n,n)$，并且棋盘上已经放上了 $n - 1$ 个互相不能攻击的车。 互相不能攻击的定义：在任何一行中最多只有一辆车，在任何一列中最多只有一辆车。 容易证明，此时该棋盘还可以放一辆车，使得所有的 $n$ 辆车互相不能攻击。 现在你想在一个位置上摆上一辆车，使得所有的 $n$ 辆车互相不能攻击，设这个位置为 $(x,y)$。但是你不知道前 $n - 1$ 辆车的位置。 不过你可以进行不超过 $20$ 次的形如 `? a b c d` 的询问，这时系统会返回左上角为 $(a,c)$，右下角为 $(b,d)$ 的子矩阵中的车的数量。**询问的前提是 $1 \leq a \leq b \leq n$，$1 \leq c \leq d \leq n$。** 你需要利用询问来求出 $(x,y)$。当你得到结果后，你应该输出形如 `! x y` 的形式，其中 $x$ 和 $y$ 的定义如上述。 注意： - 询问过后立即清空缓冲区。如果你不这么做，你可能会 TLE。 - 若你输出了无效询问（或回答），返回结果是不确定的。 - 若你在回答后不立即结束程序，返回的结果是不确定的。 $1 \leq n \leq 1000$。Output
分数：500分
问题描述
这是一个交互式任务（您的程序通过输入和输出与裁判程序交互）。
我们有一个 $N$×$N$ 的棋盘和 $N$ 个车。下面，从上数第 $i$ 行、从左数第 $j$ 列的方格表示为 $(i, j)$。
考虑将车放置在棋盘的方格上。这里，您必须放置车，以便所有以下条件都得到满足。
- 没有任何一行包含两个或更多的车。
- 没有任何一列包含两个或更多的车。
现在，已经在棋盘上放置了 $N-1$ 个车，以便所有上述条件都得到满足。您将选择一个未被车占据的方格，并在该方格上放置一个车。（可以证明，在这种条件下，棋盘上至少有一个可以放置车的方格）。
但是，您不能直接看到棋盘上哪些方格被车占据。
相反，您最多可以按照以下方式向裁判提出 $20$ 个问题。
- 您选择整数 $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$。
找到放置车的方格。
限制条件
- $2 \leq N \leq 10^3$
- $N$ 是一个整数。
输入和输出
这是一个交互式任务（您的程序通过输入和输出与裁判程序交互）。
首先，从标准输入接收棋盘的大小 $N$。
$N$
接下来，重复提问，直到找到放置车的方格。
问题应以以下格式打印到标准输出：
$?$ $A$ $B$ $C$ $D$
响应将以以下格式从标准输入给出：
$T$
这里，$T$ 是对问题的响应，或者如果问题无效或已经提出了超过 $20$ 个问题，则为 -1。
当裁判返回 -1 时，提交已经被认为是不正确的。在这种情况下，立即终止程序。
当您找到放置车的方格时，让 $(X, Y)$ 表示该方格，然后以以下格式打印答案。然后立即终止程序。
$!$ $X$ $Y$
如果有多个合适的答案，将接受其中任何一个。