Finding Zero
Contest: Codeforces Round 770 (Div. 2)
Difficulty rating: 2000
Tags: constructive algorithms, interactive, math

This is an interactive problem.

We picked an array of whole numbers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) and concealed exactly one zero in it! Your goal is to find the location of this zero, that is, to find $$$i$$$ such that $$$a_i = 0$$$.

You are allowed to make several queries to guess the answer. For each query, you can think up three distinct indices $$$i, j, k$$$, and we will tell you the value of $$$\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$$$. In other words, we will tell you the difference between the maximum and the minimum number among $$$a_i$$$, $$$a_j$$$ and $$$a_k$$$.

You are allowed to make no more than $$$2 \cdot n - 2$$$ queries, and after that you have two tries to guess where the zero is. That is, you have to tell us two numbers $$$i$$$ and $$$j$$$ and you win if $$$a_i = 0$$$ or $$$a_j = 0$$$.

Can you guess where we hid the zero?

Note that the array in each test case is fixed beforehand and will not change during the game. In other words, the interactor is not adaptive.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). Description of the test cases follows.

The first and only line of each test case contains an integer $$$n$$$ ($$$4 \le n \le 1000$$$) — the length of the array that we picked.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Interaction format:
For each test case, the interaction starts with reading $$$n$$$.

To make a query, print "? $$$i$$$ $$$j$$$ $$$k$$$" (without quotes, $$$1 \le i, j, k \le n$$$, indices must be distinct). Then you should read our response from standard input, that is, $$$\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$$$.

If the response is $$$-1$$$, it means your program has made an invalid query or has run out of tries. Your program must terminate immediately after reading $$$-1$$$, and you will get a verdict Wrong answer. Otherwise you may get any verdict, because the program will continue reading from the closed stream. Note that if the query is correct, the answer will never be $$$-1$$$ because $$$\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k) \geq 0$$$.

To give the final answer, print "! $$$i$$$ $$$j$$$" (without the quotes). Printing the same number twice (that is, $$$i = j$$$) is allowed. Note that giving this answer is not counted towards the limit of $$$2 \cdot n - 2$$$ queries. After that, your program must continue to solve the remaining test cases, or exit if all test cases have been solved.

After printing a query, don't forget to output line feed and flush the output buffer. Otherwise you will get the verdict Idleness limit exceeded. To flush the buffer, use:

- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- Read documentation for other languages.

Hacks

The first line must contain an integer $$$t$$$ ($$$1 \le t \le 500$$$) — the count of test cases.

The first line of each test case must contain an integer $$$n$$$ ($$$4 \le n \le 1000$$$) — the length of the hidden array.

The second line of each test case must contain $$$n$$$ integers separated by spaces — $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$). There must also be exactly one zero in this array.

The sum of $$$n$$$ over all test cases must not exceed $$$3000$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Array from sample: $$$[1, 2, 0, 3]$$$.

Example input:
1

4

2

3

3

2

Example output:
? 1 2 3

? 2 3 4

? 3 4 1

? 4 1 2

! 2 3

Editorial:
Notice that for any four numbers $$$a, b, c, d$$$ we can locate at least two numbers among them that are certainly not zeroes using only four queries as follows.
For each of the four numbers, compute it's complement, that is, the difference between the maximum and the minimum of the other three numbers: $$$\bar{a} = \max(b, c, d) - \min(b, c, d)$$$ and so on. This takes exactly four queries.
Now, consider what happens if one of the four numbers was a zero. For instance, if $$$a = 0, b \le c \le d$$$, then:
• $$$\bar{a} = d - b$$$
• $$$\bar{b} = d$$$
• $$$\bar{c} = d$$$
• $$$\bar{d} = c$$$
$$$d > d - b, d \ge c$$$, so the two largest complements ($$$\bar{b} = \bar{c} = d$$$ in this example) are always complements of non-zeroes. Of course, the order of the values could be different, but the numbers with the two largest complements will always be guaranteed non-zeroes.
If there is no zero among these numbers, then we can still run this algorithm because it doesn't matter exactly which numbers it will yield — they are all non-zero anyway.
Now let's learn how to solve the problem using this algorithm. Start with a "pile" of the first four numbers, apply the algorithm and throw two certain non-zeroes away. Add the next two numbers to the "pile" and drop two non-zeroes again. Repeat this until there are two or three numbers left in the "pile", depending on the parity of $$$n$$$. If there are three elements left, add some number that we have already dropped to the pile again and apply the algorithm the last time.
• If $$$n$$$ is even, we have made $$$\frac{n - 2}{2} \cdot 4 = 2n - 4$$$ queries.
• If $$$n$$$ is odd, we have made $$$\frac{n - 3}{2} \cdot 4 + 4 = 2n - 2$$$ queries.
The complexity of this solution is $$$\mathcal{O}(n)$$$, and the solution uses no more than $$$2n - 2$$$ queries.