← 返回题目列表

Codeforces · 2096/G

G. 精彩的猜谜游戏

中文机器翻译题面 查看原题

这是一个交互问题。

您是千年科学学校的一名令人自豪的老师。今天,一位名叫爱丽丝的学生向您挑战猜谜游戏。

Alice 正在考虑一个从 $$$1$$$ 到 $$$n$$$ 的整数,你必须通过询问她一些问题来猜出它。

为了让事情变得更困难,她说你必须 首先询问所有疑问,她会 忽略 正好 $$$1$$$ 查询。

对于每个查询,您选择一个 $$$k$$$ 数组 不同 从 $$$1$$$ 到 $$$n$$$ 的整数,其中 $$$k$$$ 是偶数。然后,爱丽丝将回复以下内容之一:

  • $$$\texttt{L}$$$:该数字是数组的前 $$$\frac{k}{2}$$$ 元素之一;
  • $$$\texttt{R}$$$:数字是数组最后 $$$\frac{k}{2}$$$ 元素之一;
  • $$$\texttt{N}$$$: 该数字不在数组中;
  • $$$\texttt{?}$$$:忽略此查询。

Alice 很不耐烦,所以你必须找到一个策略 最小化 查询数量。你能做到吗?

正式地,令 $$$f(n)$$$ 为确定 Alice 号码所需的最小查询数。那么你必须找到一个使用的策略 正是 $$$f(n)$$$ 查询。

请注意,交互器是 自适应,这意味着 Alice 的号码一开始并不是固定的,可能取决于您的查询。然而,可以保证至少存在一个与Alice的响应一致的数字。

我们可以证明,对于所有$$$n$$$,$$$f(n) \leq 20$$$ 使得$$$2 \le n \le 2 \cdot 10^5$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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 的号码时,输出一个整数 $$$x$$$ ($$$1 \leq x \leq n$$$) — 该号码的值。

然后,继续进行下一个测试用例,或者如果没有更多的测试用例则终止程序。

输出所有 $$$q$$$ 查询后,不要忘记输出行尾并刷新输出。否则,你会得到 超出空闲限制。为此,请使用:

  • fflush(标准输出) or cout.flush() 在 C++ 中; Java 中的
  • System.out.flush() ;
  • 冲洗(输出) 帕斯卡;
  • stdout.flush() 在 Python 中;
  • 请参阅其他语言的文档。

请注意,即使您正确确定了 Alice 的号码但使用了超过 $$$f(n)$$$ 查询,您也会得到 错误答案.

对于这个问题,黑客被禁用。

示例

输入
复制

2
3



?N

5




R?L

输出
复制


2
2 1 2
2 1 2

3

3
4 3 2 4 1
4 5 4 3 1
4 1 5 3 4

1

注意

在第一个测试用例中,$$$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$$$ 查询。