DMOPC '21 Contest 3 P1 - Sums & Differences

View as PDF

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

Author:
Problem type

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

1. Define and .
2. Set and .
3. Tell Bob the new value of .

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

Constraints

All elements of are initially integers in the range .

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 .

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 and . In response, Alice will perform the three actions described in the statement, giving Bob the value of as an integer on its own line.

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

Also, Alice does not like very large numbers, so all elements of the array must stay in the range .

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 , or you exceed the limit of questions, Alice will respond with . 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, is originally .

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

Explanation

After the first question, becomes . Alice responds with the new value of , which is .

After the second question, becomes . Alice responds with the new value of , which is .

After the third question, becomes . Alice responds with the new value of , which is .

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