← 返回题目列表

Codeforces · 2129/C1

C1. 互动RBS(简易版)

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

这是一个交互问题。

这是问题的简单版本。唯一的区别是查询数量的限制。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

有一个长度为$$$n$$$的隐藏括号序列$$$s$$$,其中$$$s$$$仅包含$$$\texttt{'('}$$$和$$$\texttt{')'}$$$。保证 $$$s$$$ 至少包含一个 $$$\texttt{'('}$$$ 和一个 $$$\texttt{')'}$$$。

要找到这个括号序列,可以提问。每个查询都具有以下形式:您选择一个整数 $$$k$$$ 和任意索引 $$$i_1, i_2, \ldots, i_k$$$ ($$$1 \le k \le 1000$$$, $$$1 \le i_1, i_2, \ldots, i_k \le n$$$)。 请注意,索引可以相等。 接下来,您会收到陪审团计算出的整数 $$$f(s_{i_1}s_{i_2}\ldots s_{i_k})$$$。

对于括号序列 $$$t$$$,$$$f(t)$$$ 是非空的个数 常规 $$$t$$$ 中的括号子字符串(子字符串必须是 连续)。例如,$$$f(\texttt{"()())"}) = 3$$$。

括号序列称为 常规 如果可以通过以下方式构建。

  1. 空序列 $$$\varnothing$$$ 是常规的。
  2. 如果括号序列 $$$A$$$ 是正则,则 $$$\mathtt{(}A\mathtt{)}$$$ 也是正则。
  3. 如果括号序列 $$$A$$$ 和 $$$B$$$ 是规则的,则连接序列 $$$A B$$$ 也是规则的。

例如,序列 $$$\texttt{"(())()"}$$$、$$$\texttt{"()"}$$$ 是常规序列,而 $$$\texttt{"(()"}$$$ 和 $$$\texttt{"())("}$$$ 不是常规序列。

使用不超过 $$$550$$$ 查询查找序列 $$$s$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20$$$)。测试用例的描述如下。

互动

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$)。此时,选择括号序列$$$s$$$。此任务中的交互器是 不自适应。换句话说,括号序列$$$s$$$在每个测试用例中都是固定的,并且在交互过程中不会改变。

要提出查询,您需要选择一个整数 $$$k$$$ 和任意索引 $$$i_1$$$, $$$i_2 \ldots i_k$$$ ($$$1 \le k \leq 1000$$$, $$$1 \leq i_1, i_2, \ldots, i_k \leq n$$$) 并打印以下表格的行(不带引号):

  • "$$$?\ k\ i_1\ i_2 \ldots i_k$$$"

之后,您会收到一个整数 $$$f(s_{i_1}s_{i_2}\ldots s_{i_k})$$$。

您最多可以通过此表单提出 $$$550$$$ 查询。

接下来,如果您的程序找到了括号序列 $$$s$$$,则按以下格式打印一行(不带引号):

  • “$$$!\ s_1s_2 \ldots s_n$$$”

请注意,这一行是 不 被认为是一个查询,并且是 不 在计算询问的数量时考虑在内。

此后,继续下一个测试用例。

如果您在交互过程中询问超过 $$$550$$$ 查询,您的程序必须立即终止,并且您将收到 错误答案 判决。否则,您可以获得任意判决,因为您的解决方案将继续从关闭的流中读取。

打印测试用例的查询或答案后,不要忘记输出行尾并刷新输出。否则,你将得到判决 超出空闲限制。为此,请使用:

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

黑客

要破解,请遵循以下测试格式。

第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 20$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 1000$$$)。

每个测试用例的第二行包含一个括号序列 $$$s_1 s_2\ldots s_{n}$$$,其中 $$$s_i= \texttt{'('}$$$ 或 $$$\texttt{')'}$$$。

括号序列 $$$s$$$ 必须至少包含一个 $$$\texttt{'('}$$$ 和一个 $$$\texttt{')'}$$$。

示例

输入
复制

2
3

0

1

1

2

3

输出
复制


? 4 1 2 3 3

? 2 2 1

? 2 3 1

! )((

? 4 1 2 1 2

! ()


注意

在第一个测试用例中,隐藏的括号序列是 $$$s=\texttt{")(("}$$$。

对于查询“? 4 1 2 3 3",陪审团返回 $$$0$$$,因为 $$$f(s_{1}s_{2}s_{3}s_{3}) = f(\texttt{")((("}) = 0$$$。

对于查询“? 2 2 1",陪审团返回 $$$1$$$,因为 $$$f(s_{2}s_{1}) = f(\texttt{"()"}) = 1$$$。

对于查询“? 2 3 1",陪审团返回 $$$1$$$,因为 $$$f(s_{3}s_{1}) = f(\texttt{"()"}) = 1$$$。

在第二个测试用例中,隐藏的括号序列是$$$s=\texttt{"()"}$$$。

对于查询“? 4 1 2 1 2",陪审团返回 $$$3$$$,因为 $$$f(s_{1}s_{2}s_{1}s_{2}) = f(\texttt{"()()"}) = 3$$$。

请注意,该示例仅用于理解该语句,并且不 不 保证找到唯一的括号序列$$$s$$$。