No.3737 Quiz Time
Problem Statement
This is an interactive problem.
You are going to play a game with Kencho.
The game is as follows.
- Kencho secretly holds his favorite $P \times P$ grid $A$. Each cell of $A$ contains exactly $1$ integer, and each integer between $1$ and $P^2$, inclusive, is written in exactly $1$ cell. Hereafter, let $A_{i, j}$ denote the integer written in the cell at the $i$-th row from the top and the $j$-th column from the left of $A$.
- You can ask the following question up to $P$ times.
- Specify a pair of integers $(i, j)$ satisfying $1 \leq i, j \leq P$. Kencho answers with $A_{i, j}$.
- After the questions, you win if you can correctly state the integers written in all cells of the grid $A$; otherwise, Kencho wins.
Thinking that your chances of winning are slim as things stand, you hired a skilled spy and obtained the following top-secret information.
- $A_{i, j} + A_{i+1, j+1} = A_{i, j+1} + A_{i+1, j}\ (1 \leq i, j \leq P-1)$ holds.
Win the game. You may assume that the information provided by the spy is correct.
Constraints
- All input values are integers.
- $2 \leq P \leq 97$
- $P$ is a prime number.
Input and Output
First, $P$ is given from standard input.
$P$
You can then ask questions. Print each question to standard output in the following format.
? $i$ $j$
The response to a question is given from standard input in the following format.
$A_{i,j}$
However, if the format or constraints of a question are violated, or if the number of questions exceeds $P$, -1 is given from standard input instead. In this case, terminate your program immediately.
To state the integers in all cells of $A$, print them to standard output in the following format.
!
$A_{1, 1}\ A_{1, 2}\ \ldots\ A_{1, P}$
$A_{2, 1}\ A_{2, 2}\ \ldots\ A_{2, P}$
$\vdots$
$A_{P, 1}\ A_{P, 2}\ \ldots\ A_{P, P}$
After that, terminate your program immediately.
End each output with a newline and flush standard output.
Notes
- You must flush standard output after each output.
- After asking a question, you must always receive its response.
- After printing the determined $A$, you must terminate your program immediately.
- $A$ is fixed in advance for each test case and does not change during the interaction depending on your questions.
Sample Interaction
In this case, $A_{1, 1} = 2, A_{1, 2} = 4, A_{2, 1} = 1, A_{2, 2} = 3$.
| Input | Output | Explanation |
|---|---|---|
2 | $P = 2$ is given. | |
? 1 2 | Ask a question choosing $(i, j) = (1, 2)$. | |
4 | $A_{1, 2} = 4$ is returned as the response. | |
? 2 1 | Ask a question choosing $(i, j) = (2, 1)$. | |
1 | $A_{2, 1} = 1$ is returned as the response. | |
! | Answer with $A_{1, 1} = 2, A_{1, 2} = 4, A_{2, 1} = 1, A_{2, 2} = 3$. | |
| The responses to the questions above alone do not uniquely determine $A$, but in this example the printed grid matches the actual $A$, so it is judged correct. |
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。