310268: CF1807E. Interview
Description
This is an interactive problem. If you are unsure how interactive problems work, then it is recommended to read the guide for participants.
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.
InputThe 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.
The first line of each test case contains a single integer $n$ ($1 \leq n \leq 2 \cdot 10^5$) — the number of piles.
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.
It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
After reading the input for each test case, proceed with the interaction as follows.
InteractionYou can perform the operation at most $\mathbf{30}$ times to guess the pile.
To make a guess, print a line with the following format:
- $\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.
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$).
After that, move on to the next test case, or terminate the program if there are no more test cases remaining.
If your program performs more than $30$ operations for one test case or makes an invalid query, you may receive a Wrong Answer verdict.
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:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
It is additionally recommended to read the interactive problems guide for participants.
Hacks
To make a hack, use the following format.
The first line should contain a single integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.
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.
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.
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.
ExampleInput2 5 1 2 3 4 5 11 6 3 7 1 2 3 5 3 4 2 12 6Output
? 4 1 2 3 4 ? 2 2 3 ? 1 2 ! 2 ? 4 2 3 5 6 ? 2 1 4 ! 7Note
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.
Input
题意翻译
```director``` 有 $n$ 堆石头，其中 $n-1$ 堆都只有重量为一克的石头，剩下一堆有则有一块有两克的石头和若干重量为一克的石头。 你的任务是在 $30$ 次询问内推理出那一堆有重量为两克的石头是第几堆。 首先输入 $n$，接下来输入 $n$ 个数 $a_1,a_2\dots a_n$，其中 $a_i$ 表示第 $i$ 堆有 $a_i$ 块石头。 一共有 $t$ 组数据。 每次询问你需要输出 ```?``` 这个符号，然后输出 $k $ 及 $p_1,p_2\dots p_k$（用空格隔开），表示询问 $p_1,p_2\dots p_k$ 这 $k$ 堆石头的总重量，然后你需要输入一个数 $x$ 表示你刚刚询问得到的答案。 如果你推理出来答案，输出 ```!``` 这个符号以及你得到的答案 $m$。 如果你的询问次数大于 $30$ 次，或有非法的询问，将会得到 ```Wrong Answer``` 评测结果。 记得每次输出后，都要输出一行代码来刷新缓冲区，否则会得到 ```Idleness limit exceeded``` 评测结果或其他评测结果。 - 对于 ```C++```，输出 ```fflush(stdout)``` 或 ```cout.flush()``` - 对于 ```Java```，输出 ```System.out.flush()``` - 对于 ```Pascal```，输出 ```flush(output)``` - 对于 ```Python```，输出 ```stdout.flush()``` by @[Larryyu](https://www.luogu.com.cn/user/475329)Output
这是一个交互式问题。在考试的最后阶段之前，主任进行了一次面试。他给了Gon n堆石头，第i堆有a_i块石头。每块石头都是相同的，重1克，但有一块特殊的石头是未知的堆的一部分，重2克。Gon只能问主任一种问题：他可以选择k堆，然后主任会告诉他所选堆的总重量。更正式地说，Gon可以选择一个整数k (1≤k≤n)和k个不同的堆p_1, p_2, …, p_k (1≤p_i≤n)，然后主任将返回总重量m_{p_1} + m_{p_2} + … + m_{p_k}，其中m_i表示第i堆的重量。Gon的任务是找到包含特殊石头的堆。但是，主任很忙。帮助Gon在最多30个查询中找到这个堆。
输入输出数据格式：
输入数据包含多个测试用例。第一行包含一个整数t (1≤t≤1000) - 测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n (1≤n≤2×10^5) - 堆的数量。
每个测试用例的第二行包含n个整数a_i (1≤a_i≤10^4) - 每堆石头的数量。
保证所有测试用例的n之和不超过2×10^5。
读取每个测试用例的输入后，按照以下方式进行交互。
交互：
最多可以执行30次操作来猜测堆。
为了进行猜测，请按照以下格式打印一行：
? k p_1 p_2 p_3 ... p_{k-1} p_k (1≤k≤n; 1≤p_i≤n; 所有p_i都是不同的) - 堆的索引。
每次操作后，你应该读取一行，其中包含一个整数x - 所选堆的重量之和。(形式上，x = m_{p_1} + m_{p_2} + … + m_{p_k}。)
当你知道包含特殊石头的堆的索引时，按照以下格式打印一行：
! m (1≤m≤n)。
之后，继续下一个测试用例，如果没有更多的测试用例，则结束程序。
如果你的程序对一个测试用例执行了超过30次操作或进行了无效查询，你可能会得到一个“错误答案”的判断。
在打印查询或答案后，请记得输出行尾并刷新输出。否则，你可能会得到“闲置超时”或其他判断。为此，请使用以下命令：
- 在C++中：fflush(stdout) 或 cout.flush()；
- 在Java中：System.out.flush()；
- 在Pascal中：flush(output)；
- 在Python中：stdout.flush()；
- 其他语言的文档中有说明。
示例输入输出：
输入：
2
5
1 2 3 4 5
11
6
3
7
1 2 3 5 3 4 2
12
6
输出：
? 4 1 2 3 4
? 2 2 3
? 1 2
! 2
? 4 2 3 5 6
? 2 1 4
! 7
注意：
在第一个测试用例中，重量为2的石头位于堆2中，如图所示。我们进行以下交互：
- ? 4 1 2 3 4 - 询问堆1、2、3和4的总重量。我们收到的总重量是1+3+3+4=11。
- ? 2 2 3 - 询问堆2和3的总重量。我们收到的总重量是3+3=6。
- ? 1 2 - 询问堆2的总重量。我们收到的总重量是3。
- ! 2 - 我们发现堆2包含特殊石头，所以我们输出它并继续下一个测试用例。
在第二个测试用例中，重量为2的石头位于索引7上。我们进行以下交互：
- ? 4 2 3 5 6 - 询问堆2、3、5和6的总重量。我们收到的总重量是2+3+3+4=12。
- ? 2 1 4 - 询问堆1和4的总重量。我们收到的总重量是1+5=6。
- ! 7 - 我们已经以某种方式确定堆7包含特殊石头，所以我们输出它并结束交互。题目大意： 这是一个交互式问题。在考试的最后阶段之前，主任进行了一次面试。他给了Gon n堆石头，第i堆有a_i块石头。每块石头都是相同的，重1克，但有一块特殊的石头是未知的堆的一部分，重2克。Gon只能问主任一种问题：他可以选择k堆，然后主任会告诉他所选堆的总重量。更正式地说，Gon可以选择一个整数k (1≤k≤n)和k个不同的堆p_1, p_2, …, p_k (1≤p_i≤n)，然后主任将返回总重量m_{p_1} + m_{p_2} + … + m_{p_k}，其中m_i表示第i堆的重量。Gon的任务是找到包含特殊石头的堆。但是，主任很忙。帮助Gon在最多30个查询中找到这个堆。 输入输出数据格式： 输入数据包含多个测试用例。第一行包含一个整数t (1≤t≤1000) - 测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n (1≤n≤2×10^5) - 堆的数量。 每个测试用例的第二行包含n个整数a_i (1≤a_i≤10^4) - 每堆石头的数量。 保证所有测试用例的n之和不超过2×10^5。 读取每个测试用例的输入后，按照以下方式进行交互。 交互： 最多可以执行30次操作来猜测堆。 为了进行猜测，请按照以下格式打印一行： ? k p_1 p_2 p_3 ... p_{k-1} p_k (1≤k≤n; 1≤p_i≤n; 所有p_i都是不同的) - 堆的索引。 每次操作后，你应该读取一行，其中包含一个整数x - 所选堆的重量之和。(形式上，x = m_{p_1} + m_{p_2} + … + m_{p_k}。) 当你知道包含特殊石头的堆的索引时，按照以下格式打印一行： ! m (1≤m≤n)。 之后，继续下一个测试用例，如果没有更多的测试用例，则结束程序。 如果你的程序对一个测试用例执行了超过30次操作或进行了无效查询，你可能会得到一个“错误答案”的判断。 在打印查询或答案后，请记得输出行尾并刷新输出。否则，你可能会得到“闲置超时”或其他判断。为此，请使用以下命令： - 在C++中：fflush(stdout) 或 cout.flush()； - 在Java中：System.out.flush()； - 在Pascal中：flush(output)； - 在Python中：stdout.flush()； - 其他语言的文档中有说明。 示例输入输出： 输入： 2 5 1 2 3 4 5 11 6 3 7 1 2 3 5 3 4 2 12 6 输出： ? 4 1 2 3 4 ? 2 2 3 ? 1 2 ! 2 ? 4 2 3 5 6 ? 2 1 4 ! 7 注意： 在第一个测试用例中，重量为2的石头位于堆2中，如图所示。我们进行以下交互： - ? 4 1 2 3 4 - 询问堆1、2、3和4的总重量。我们收到的总重量是1+3+3+4=11。 - ? 2 2 3 - 询问堆2和3的总重量。我们收到的总重量是3+3=6。 - ? 1 2 - 询问堆2的总重量。我们收到的总重量是3。 - ! 2 - 我们发现堆2包含特殊石头，所以我们输出它并继续下一个测试用例。 在第二个测试用例中，重量为2的石头位于索引7上。我们进行以下交互： - ? 4 2 3 5 6 - 询问堆2、3、5和6的总重量。我们收到的总重量是2+3+3+4=12。 - ? 2 1 4 - 询问堆1和4的总重量。我们收到的总重量是1+5=6。 - ! 7 - 我们已经以某种方式确定堆7包含特殊石头，所以我们输出它并结束交互。