codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1807E.md (5315B)


      1 Source: https://codeforces.com/problemset/problem/1807/E
      2 
      3 E. Interview
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 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).
     22 
     23 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.
     24 
     25 Each stone is identical and weighs $1$ grams, except for one special stone that is part of an unknown pile and weighs $2$ grams.
     26 
     27  ![](https://espresso.codeforces.com/0c7718df31a14a12caff203c2239a3e033843f83.png) A picture of the first test case. Pile $2$ has the special stone. The piles have weights of $1,3,3,4,5$, respectively. 
     28 
     29 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$.
     30 
     31 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.
     32 
     33 Input
     34 
     35 The input data contains several test cases. The first line contains one integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The description of the test cases follows.
     36 
     37 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of piles.
     38 
     39 The second line of each test case contains $n$ integers $a_i$ ($1 \leq a_i \leq 10^4$) — the number of stones in each pile.
     40 
     41 It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     42 
     43 After reading the input for each test case, proceed with the interaction as follows.
     44 
     45 Interaction
     46 
     47 You can perform the operation at most $\mathbf{30}$ times to guess the pile.
     48 
     49 To make a guess, print a line with the following format:
     50 
     51 * $\texttt{?}\ k \ p_1 \ p_2 \ p_3 \ ... \ p_{k-1}\ p_k$ ($1 \leq k \leq n$; $1 \leq p_i \leq n$; all $p_i$ are distinct) — the indices of the piles.
     52 
     53 After each operation, you should read a line containing a single integer $x$ — the sum of weights of the chosen piles. (Formally, $x = m_{p_1} + m_{p_2} + \dots + m_{p_k}$.)
     54 
     55 When you know the index of the pile with the special stone, print one line in the following format: $\texttt{!}\ m$ ($1 \leq m \leq n$).
     56 
     57 After that, move on to the next test case, or terminate the program if there are no more test cases remaining.
     58 
     59 If your program performs more than $30$ operations for one test case or makes an invalid query, you may receive a Wrong Answer verdict.
     60 
     61 After you print a query or the answer, please remember to output the end of the line and flush the output. Otherwise, you may get Idleness limit exceeded or some other verdict. To do this, use the following:
     62 
     63 * fflush(stdout) or cout.flush() in C++;
     64 * System.out.flush() in Java;
     65 * flush(output) in Pascal;
     66 * stdout.flush() in Python;
     67 * see the documentation for other languages.
     68 
     69 It is additionally recommended to read the [interactive problems guide for participants](https://codeforces.com/blog/entry/45307).
     70 
     71 Hacks
     72 
     73 To make a hack, use the following format.
     74 
     75 The first line should contain a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
     76 
     77 The first line of each test case should contain two integers $n, m$ ($1 \leq n \leq 2 \cdot 10^5$) – the number of piles and the pile with the special stone.
     78 
     79 The second line of each test case should contain $n$ integers $a_i$ ($1 \leq a_i \leq 10^4$) — the number of stones in each pile.
     80 
     81 Note that the interactor is not adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.
     82 
     83 Example
     84 
     85 Input
     86 
     87 ```
     88 2
     89 5
     90 1 2 3 4 5
     91 
     92 11
     93 
     94 6
     95 
     96 3
     97 
     98 7
     99 1 2 3 5 3 4 2
    100 
    101 12
    102 
    103 6
    104 ```
    105 
    106 Output
    107 
    108 ```
    109 ? 4 1 2 3 4
    110 
    111 ? 2 2 3
    112 
    113 ? 1 2
    114 
    115 ! 2
    116 
    117 ? 4 2 3 5 6
    118 
    119 ? 2 1 4
    120 
    121 ! 7
    122 ```
    123 
    124 Note
    125 
    126 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:
    127 
    128 * $\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$.
    129 * $\texttt{? 2 2 3}$ — ask the total weight of piles $2$ and $3$. The total weight we receive back is $3+3=6$.
    130 * $\texttt{? 1 2}$ — ask the total weight of pile $2$. The total weight we receive back is $3$.
    131 * $\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.
    132 
    133 In the second test case, the stone with weight two is located on index $7$. We perform the following interaction:
    134 
    135 * $\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$.
    136 * $\texttt{? 2 1 4}$ — ask the total weight of piles $1$ and $4$. The total weight we receive back is $1+5=6$.
    137 * $\texttt{! 7}$ — we have somehow figured out that pile $7$ contains the special stone, so we output it and end the interaction.