DMOPC '21 Contest 3 P1 - Sums & Differences

View as PDF

Submit solution

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

Problem types

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?


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.


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

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


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.


There are no comments at the moment.