CF2273E Six-Seven Bags

这是一个交互题。 Ale 和 Sofia 想要在城市里的每场 aura 战斗中获胜，因此她们正在用装满硬币的袋子准备一场街头魔术。 桌上有 $n$ 个袋子，第 $i$ 个袋子里有 $a_i$ 枚硬币。每个袋子中的硬币类型相同：要么都是 $6$ 克的硬币，要么都是 $7$ 克的硬币。恰好有一个袋子装的是 $6$ 克的硬币，其他 $n-1$ 个袋子装的都是 $7$ 克的硬币。Ale 和 Sofia 知道数组 $a$，但不知道哪个袋子装的是 $6$ 克硬币。 每进行一次查询，你可以从每个袋子中任选数量（可以为零）取出硬币，并知道这些硬币的总重量。每次查询后所有取出的硬币都会放回原袋。 设 $f(a)$ 为无论 $6$ 克袋子的下标是哪一个都可以保证找到 $6$ 克袋子的最少查询次数。请你帮助 Ale 和 Sofia 用不超过 $f(a)$ 次查询确定 $6$ 克袋子的位置。 判题器是自适应的。在交互过程中，$6$ 克硬币所在的袋子下标可能发生变化，只要所有之前的回答都能自洽即可。

每个测试点包含多组测试用例。第一行输入一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。 每组测试用例的第一行输入一个整数 $n$（$2 \le n \le 10^5$），表示袋子总数。 第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$1 \le a_i \le n$），表示每个袋子中的硬币数。 保证所有测试用例 $n$ 的总和不超过 $10^5$。

无

示例交互并非最优策略，仅为演示输入输出格式。 示例中的额外空行仅为提升可读性，实际交互中没有。 在第一个测试点中，$n=5$，$a=[1,1,2,2,2]$。第三个袋子装 $6$ 克的硬币。比如查询 ? 1 0 1 2 1：共选 5 枚硬币，其中 $b_3 = 1$，总质量为 $7 \times (1 + 0 + 2 + 1) + 6 \times 1 = 34$。 再比如 ? 1 1 2 0 1：共选 5 枚硬币，其中 $b_3 = 2$，总质量为 $7 \times (1 + 1 + 0 + 1) + 6 \times 2 = 33$。 随后输出 ! 3，确定第 3 个袋子。 在第二个测试点中，$n=4$，$a=[3,2,4,3]$。第二个袋子装 $6$ 克硬币。查询 ? 3 2 2 0，即从第二袋中取出 2 枚硬币（共 7 枚），返回 $7 \times (3 + 2 + 0) + 6 \times 2 = 47$。 随后输出 ! 2。对于交互中的隐藏袋子选择，该答案是正确的，但此查询不能区分第二袋与第三袋。 由 ChatGPT 5 翻译