E - Last Rook 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 500 点

問題文

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。

縦横 N マスのチェス盤と N 個のルークの駒があります。以下では上から i 行目、左から j 列目のマスを (i, j) と表します。
チェス盤のマスにルークを置くことを考えます。ただし、あなたは次の条件をすべて満たすようにルークをチェス盤に置く必要があります。

  • 1 つの行に 2 個以上のルークが存在しない。
  • 1 つの列に 2 個以上のルークが存在しない。

今、チェス盤に N-1 個のルークが上の条件をすべて満たした状態で置かれています。あなたはルークが置かれていないマスを 1 つ選び、そのマスにルークを置くことにしました。(上の条件をすべて満たすようにルークを置くことができるマスは少なくとも 1 つ以上存在することが証明できます。)

ただし、あなたはチェス盤のどのマスにルークが置かれているかを直接知ることはできません。
そのかわりに、ジャッジシステムに対して以下の質問を 20 回まで行うことができます。

  • 整数 A, B, C, D を 1 \leq A \leq B \leq N, 1 \leq C \leq D \leq N を満たすように選ぶ。そして、A \leq i \leq B, C \leq j \leq D を満たすマス (i, j) からなる長方形領域に置かれているルークの個数を聞く。

ルークを置くことができるマスを見つけてください。

制約

  • 2 \leq N \leq 10^3
  • N は整数

入出力

この問題はインタラクティブな問題（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。

最初に、チェス盤のサイズ N を標準入力から受け取ってください。

N

次に、ルークを置くことができるマスが見つかるまで質問を繰り返してください。
質問は、以下の形式で標準出力に出力してください。

? A B C D

これに対する応答は、次の形式で標準入力から与えられます。

T

ここで、T は質問に対する答えです。ただし、不正な質問を行った、あるいは質問の回数が 20 回を超えた場合は T は -1 となります。

ジャッジが -1 を返した場合、提出はすでに不正解とみなされています。この場合、ただちにプログラムを終了してください。

ルークを置くことができるマスを見つけたら、そのマスを (X, Y) として、解答を以下の形式で出力してください。その後、ただちにプログラムを終了してください。

! X Y

答えが複数ある場合、どれを出力しても正解とみなされます。

注意点

  • 出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。
  • 対話の途中で不正な出力を行った場合のジャッジ結果は不定です。
  • 解答を出力したらただちにプログラムを終了してください。そうしない場合、ジャッジ結果は不定です。

入出力例

以下は、N=3 で (1, 2), (2, 1) にルークが置かれている場合の入出力例です。

入力 出力 説明
3 まず整数 N が与えられます。
? 1 2 1 3 (A,B,C,D)=(1,2,1,3) として質問を行います。
2 質問の答えは 2 なので、ジャッジはその値を返します。
? 2 3 1 1 (A,B,C,D)=(2,3,1,1) として質問を行います。
1 質問の答えは 1 なので、ジャッジはその値を返します。
? 1 3 3 3 (A,B,C,D)=(1,3,3,3) として質問を行います。
0 質問の答えは 0 なので、ジャッジはその値を返します。
! 3 3 答えは (3, 3) だとわかったので、それを出力します。

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 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.