CF2096G Wonderful Guessing Game

这是一道交互题。 你是千年科学学校的一名自豪的教师。今天，一名叫 Alice 的学生向你发起了一个猜数游戏的挑战。 Alice 心中想着一个 $1$ 到 $n$ 之间的整数，你必须通过向她提出一些查询来猜出这个数。 为了增加难度，她要求你必须先提出所有查询，而她将忽略其中的恰好 $1$ 个查询。 对于每个查询，你需要选择一个由 $1$ 到 $n$ 之间的 $k$ 个不同整数组成的数组，其中 $k$ 是偶数。然后，Alice 会给出以下回应之一： - $\texttt{L}$：这个数位于数组的前 $\frac{k}{2}$ 个元素中； - $\texttt{R}$：这个数位于数组的后 $\frac{k}{2}$ 个元素中； - $\texttt{N}$：这个数不在数组中； - $\texttt{?}$：这个查询被忽略。 Alice 很没耐心，因此你必须找到一种策略，使得查询次数最少。你能做到吗？ 形式化地说，设 $f(n)$ 为确定 Alice 的数字所需的最小查询次数。你需要找到一种恰好使用 $f(n)$ 次查询的策略。 注意，交互器是自适应的，这意味着 Alice 的数字并非一开始就固定，可能会根据你的查询而变化。然而，保证至少存在一个数字与 Alice 的回应一致。 我们可以证明，对于所有满足 $2 \le n \le 2 \cdot 10^5$ 的 $n$，$f(n) \leq 20$。

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。接下来是每个测试用例的描述。 每个测试用例的唯一一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$）——Alice 的数字的最大可能值。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

交互开始时，先读取整数 $n$。 然后，输出一个整数 $q$（$1 \leq q \leq 20$）——查询的次数。 要提出一个查询，请按以下格式输出一行： - $k\,a_1\,a_2 \ldots a_k$（$2 \leq k \leq n$，$k$ 是偶数，$1 \leq a_i \leq n$，$a_i$ 互不相同）——数组的长度和数组本身。 在提出所有 $q$ 次查询后，读取一个字符串 $s$（$|s| = q$）——Alice 对查询的回应，如上所述。 当你确定 Alice 的数字时，输出一个整数 $x$（$1 \leq x \leq n$）——这个数字的值。 然后，继续处理下一个测试用例，如果没有更多测试用例，则终止程序。 在输出所有 $q$ 次查询后，不要忘记输出换行并刷新输出。否则，你将得到 Idleness limit exceeded。为此，请使用： - C++ 中的 `fflush(stdout)` 或 `cout.flush()`； - Java 中的 `System.out.flush()`； - Pascal 中的 `flush(output)`； - Python 中的 `stdout.flush()`； - 其他语言的类似方法。 注意，即使你正确猜出了 Alice 的数字，但如果使用的查询次数超过了 $f(n)$，你也会得到 Wrong answer。 本题禁用 hack。

在第一个测试用例中，$n = 3$。我们提出了 $2$ 次查询：$[1, 2]$ 和再次的 $[1, 2]$。 - 对于第一次查询，Alice 的回应是 $\texttt{?}$，表示这次查询被忽略。 - 对于第二次查询，Alice 的回应是 $\texttt{N}$，表示她的数字不在数组 $[1, 2]$ 中。 根据以上信息，我们可以确定 Alice 的数字是 $3$。 可以证明，对于 $n = 3$，所有有效策略至少需要 $2$ 次查询。 在第二个测试用例中，$n = 5$。我们提出了 $3$ 次查询：$[3, 2, 4, 1]$、$[5, 4, 3, 1]$ 和 $[1, 5, 3, 4]$。 - 对于第一次查询，Alice 的回应是 $\texttt{R}$，表示她的数字在数组 $[4, 1]$ 中。 - 对于第二次查询，Alice 的回应是 $\texttt{?}$，表示这次查询被忽略。 - 对于第三次查询，Alice 的回应是 $\texttt{L}$，表示她的数字在数组 $[1, 5]$ 中。 根据以上信息，我们可以确定 Alice 的数字是 $1$。 可以证明，对于 $n = 5$，所有有效策略至少需要 $3$ 次查询。 翻译由 DeepSeek V3 完成