DMOPC '21 Contest 3 P1 - Sums & Differences

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

Alice is playing a game with Bob. She hides an array A of N integers from Bob, and asks him to guess the numbers in it. In a single question, if Bob gives Alice a pair of indices (i, j) with i \neq j, Alice does the following actions in order:

  1. Define x := A_i and y := A_j.
  2. Set A_i := x + y and A_j := x - y.
  3. Tell Bob the new value of A_j.

Alice allows at most N questions from Bob. Can you help him figure out the original array (that is, the array A before Alice performs any operations on it)?

Constraints

2 \le N \le 10^4

All elements of A are initially integers in the range [-10^9, 10^9].

Subtask 1 [20%]

N = 2

Subtask 2 [20%]

N = 3

Subtask 3 [60%]

No additional constraints.

Interaction

This is an interactive problem, where you and the judge exchange information back-and-forth to solve the problem.

At first, you should read in a line containing the integer N.

You will then start the interaction by proceeding with your questions. Each question should be formatted as ? i j followed by a \n character, with 1 \le i, j \le N and i \neq j. In response, Alice will perform the three actions described in the statement, giving Bob the value of A_j as an integer on its own line.

If you believe you have the solution, you may output ! followed by a space-separated list of N integers A_1, A_2, \dots, A_N, the original elements of A. You must terminate your program immediately after performing this operation. Note that this operation does not count towards the limit of N questions.

Also, Alice does not like very large numbers, so all elements of the array must stay in the range [-10^{18}, 10^{18}].

If at any point you attempt an invalid question (such as an invalid output format or a prohibited pair of indices), an element of the array goes out of the range [-10^{18}, 10^{18}], or you exceed the limit of N questions, Alice will respond with 10^{18} + 1. You should terminate your program immediately after receiving this feedback to receive a Wrong Answer verdict, or you may receive an arbitrary verdict. If the final list you output is incorrect, you will receive a Wrong Answer verdict. Otherwise, you will receive a verdict of Accepted for the corresponding test case.

Please note that you may need to flush stdout after each operation, or interaction may halt. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

In this case, A is originally [2, 5, 4].

3
>>> ? 2 1
3
>>> ? 1 3
-1
>>> ? 2 3
8
>>> ! 2 5 4

Explanation

After the first question, A becomes [3, 7, 4]. Alice responds with the new value of A_j, which is 3.

After the second question, A becomes [7, 7, -1]. Alice responds with the new value of A_j, which is -1.

After the third question, A becomes [7, 6, 8]. Alice responds with the new value of A_j, which is 8.

This interaction would receive an Accepted verdict, since it correctly guessed the original list of numbers after asking no more than N questions. Note that the interaction may not represent an optimal or correct strategy to solve the problem, and is only presented for clarity purposes.


Comments

There are no comments at the moment.