CF1807E Interview

This is an interactive problem. If you are unsure how interactive problems work, then it is recommended to read [the guide for participants](https://codeforces.com/blog/entry/45307). Before the last stage of the exam, the director conducted an interview. He gave Gon $ n $ piles of stones, the $ i $ -th pile having $ a_i $ stones. Each stone is identical and weighs $ 1 $ grams, except for one special stone that is part of an unknown pile and weighs $ 2 $ grams.  A picture of the first test case. Pile $ 2 $ has the special stone. The piles have weights of $ 1,3,3,4,5 $ , respectively.Gon can only ask the director questions of one kind: he can choose $ k $ piles, and the director will tell him the total weight of the piles chosen. More formally, Gon can choose an integer $ k $ ( $ 1 \leq k \leq n $ ) and $ k $ unique piles $ p_1, p_2, \dots, p_k $ ( $ 1 \leq p_i \leq n $ ), and the director will return the total weight $ m_{p_1} + m_{p_2} + \dots + m_{p_k} $ , where $ m_i $ denotes the weight of pile $ i $ . Gon is tasked with finding the pile that contains the special stone. However, the director is busy. Help Gon find this pile in at most $ \mathbf{30} $ queries.

N/A

N/A

In the first test case, the stone with weight two is located in pile $ 2 $ , as shown in the picture. We perform the following interaction: - $ \texttt{? 4 1 2 3 4} $ — ask the total weight of piles $ 1 $ , $ 2 $ , $ 3 $ , and $ 4 $ . The total weight we receive back is $ 1+3+3+4=11 $ . - $ \texttt{? 2 2 3} $ — ask the total weight of piles $ 2 $ and $ 3 $ . The total weight we receive back is $ 3+3=6 $ . - $ \texttt{? 1 2} $ — ask the total weight of pile $ 2 $ . The total weight we receive back is $ 3 $ . - $ \texttt{! 2} $ — we have figured out that pile $ 2 $ contains the special stone, so we output it and move on to the next test case. In the second test case, the stone with weight two is located on index $ 7 $ . We perform the following interaction: - $ \texttt{? 4 2 3 5 6} $ — ask the total weight of piles $ 2 $ , $ 3 $ , $ 5 $ , and $ 6 $ . The total weight we receive back is $ 2+3+3+4=12 $ . - $ \texttt{? 2 1 4} $ — ask the total weight of piles $ 1 $ and $ 4 $ . The total weight we receive back is $ 1+5=6 $ . - $ \texttt{! 7} $ — we have somehow figured out that pile $ 7 $ contains the special stone, so we output it and end the interaction.