CF2273E Six-Seven Bags

This is an interactive problem. Ale and Sofia want to win every aura battle in the city, so they are preparing a street-magic trick with bags of coins. There are $ n $ bags on a table. The $ i $ -th bag contains $ a_i $ coins. In every bag, all coins are of the same type: either $ 6 $ -coins, which weigh $ 6 $ grams each, or $ 7 $ -coins, which weigh $ 7 $ grams each. Exactly one bag contains $ 6 $ -coins, and the other $ n - 1 $ bags contain $ 7 $ -coins. Ale and Sofia know the array $ a $ , but not which bag contains the $ 6 $ -coins. In one query, they may select any number of coins from each bag (possibly zero) and learn their total weight. All selected coins are returned to their bags after each query. Let $ f(a) $ be the minimum number of queries needed to guarantee finding the $ 6 $ -coin bag, regardless of which bag it is. Help Ale and Sofia find this bag using at most $ f(a) $ queries. The interactor is adaptive. The index of the $ 6 $ -coin bag may change during the interaction, as long as all previous answers remain consistent.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \le n \le 10^5 $ ) — the number of bags. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — the number of coins in each bag. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 10^5 $ .

N/A

The example interaction does not represent an optimal strategy and is only shown to demonstrate the input/output format. The extra blank lines in the example are for readability only and are not part of the actual input or output. In the first test case, $ n = 5 $ and $ a = [1, 1, 2, 2, 2] $ . The third bag contains $ 6 $ -coins. The displayed weights are calculated as follows: - ? 1 0 1 2 1: five coins are selected and $ b_3 = 1 $ , giving $ 7 \cdot (1 + 0 + 2 + 1) + 6 \cdot 1 = 34 $ . - ? 1 1 2 0 1: five coins are selected and $ b_3 = 2 $ , giving $ 7 \cdot (1 + 1 + 0 + 1) + 6 \cdot 2 = 33 $ . The participant then outputs ! 3 to identify the third bag.In the second test case, $ n = 4 $ and $ a = [3, 2, 4, 3] $ . The second bag contains $ 6 $ -coins. The query ? 3 2 2 0 selects seven coins, including two from the second bag, so the response is $ 7 \cdot (3 + 2 + 0) + 6 \cdot 2 = 47 $ . The participant then outputs ! 2. This answer is correct for the illustrated choice of the hidden bag, but the query does not distinguish the second bag from the third bag.