2209C. Find the Zero

constructive algorithms, interactive,https://codeforces.com/problemset/problem/2209/C

This is an interactive problem.

You are given an integer 𝑛. There is a hidden array 𝑎 of length 2𝑛. Each integer from 1 to 𝑛 appears exactly once in 𝑎. The rest of the elements are all 0.

You can make the following type of query:

Choose two integers 𝑖 and 𝑗 (1≤𝑖,𝑗≤2𝑛, 𝑖≠𝑗). The judge will respond with 1 if 𝑎𝑖=𝑎𝑗, and will respond with 0 otherwise.

Find any integer 𝑘 (1≤𝑘≤2𝑛) such that 𝑎𝑘=0 in no more than 𝑛+1 queries. Note that the interactor is adaptive, which means that the hidden array 𝑎 may change depending on your queries but will not contradict previous queries.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤103). The description of the test cases follows.

The first line of each test case contains an integer 𝑛 (2≤𝑛≤104). The length of the hidden array 𝑎 will be 2𝑛.

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 104.

Interaction

To make a query, output a line in the following format:

?𝑖𝑗 (1≤𝑖,𝑗≤2𝑛, 𝑖≠𝑗)

As a response to the query, you will get:

1 if 𝑎𝑖=𝑎𝑗;
0 if 𝑎𝑖≠𝑎𝑗;
−1 if you made an invalid query or if you exceed the limit of 𝑛+1 queries.

To report the answer, output a line in the following format:

!𝑘 (1≤𝑘≤2𝑛)

After this, proceed to the next test case or terminate if this is the last test case.

Note that reporting the answer does not count towards the 𝑛+1 queries.

The interactor is adaptive. This means that the hidden array 𝑎 may change depending on your queries but will not contradict previous queries.

After printing each query do not forget to output the end of line and flush∗ the output. Otherwise, you will get Idleness limit exceeded verdict. If, at any interaction step, you read −1 instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

For this problem, hacks are disabled.

∗To flush, use:

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Example

input

output

Note

In the first example test case, the hidden array 𝑎 is [0,1,0,2]:

In the first query, (𝑖,𝑗)=(1,2). Since 𝑎1=0, 𝑎2=1, 𝑎1≠𝑎2, the judge responds with 0.
In the second query, (𝑖,𝑗)=(3,1). Since 𝑎3=0, 𝑎1=0, 𝑎3=𝑎1, the judge responds with 1.
The program reports 𝑘=3 as an answer. Since 𝑎3=0, the answer is correct.

In the second example test case, the hidden array 𝑎 is [3,2,0,1,0,0]:

In the first query, (𝑖,𝑗)=(5,6). Since 𝑎5=0, 𝑎6=0, 𝑎5=𝑎6, the judge responds with 1.
In the second query, (𝑖,𝑗)=(2,4). Since 𝑎2=2, 𝑎4=1, 𝑎2≠𝑎4, the judge responds with 0.
In the third query, (𝑖,𝑗)=(1,3). Since 𝑎1=3, 𝑎3=0, 𝑎1≠𝑎3, the judge responds with 0.
The program reports 𝑘=6 as an answer. Since 𝑎6=0, the answer is correct.

【尹显齐物院】看到这个题，我瞬间产生了两种思路：

一、询问第 $2 i$ 和第 $2 i + 1$ 个是否相同，如果相同就直接找到了，如果总共的 $n$ 次询问都不同，这说明所有的第 $2 i$ 和第 $2 i + 1$ 个必定只有一个 $0$ ，此时再询问两次就能确定一个 $0$ 。但是这样使用了 $n + 2$ 次询问。

二、每三个数两两询问一次，共三次，如果里面有一组相同，那么里面有两个 $0$ ，并且可以确定位置。这个方法需要大约 $1.5 n$ 次，也不行。

所以，我们只要组合这两个方法就可以了，对前三个数，两两询问一次，共三次。如果没有数相等，说明这三个数里至多一个 $0$ 。对后面 $2 n - 4$ 个数，使用方法一。这样，我们进行了 $n + 1$ 次询问，并且能确定 $0$ 的位置：如果前面出现过相等的结果，那么不用多说；如果这 $n + 1$ 的询问结果都是不同，那么前面必定有 $n - 1$ 个 $0$ ，也即最后一个必定是 $0$ 。

python

for _ in range(int(input())):
    n = int(input())
    found = 0
    for i,j in [(1,2),(1,3),(2,3)]:
        print(f"? {i} {j}")
        if int(input()):
            print(f"! {i}")
            found = 1
            break
    if not found:
        for k in range(n-2):
            print(f"? {4+2*k} {5+2*k}")
            if int(input()):
                print(f"! {4+2*k}")
                found = 1
                break
    if not found:
        print(f"! {2*n}")

2209C. Find the Zero ​

2209C. Find the Zero