CF2129C1 Interactive RBS (Easy Version)

这是一个交互题。 这是该题目的简单版本。唯一的区别在于查询次数的限制。只有在所有版本的题目都被解决后，你才能进行 Hack。 有一个长度为 $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$ 都是正规括号序列，则它们的连接 $AB$ 也是正规括号序列。 例如，序列 $\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$ 次查询，你的程序必须立即终止，并且你会收到 Wrong Answer 判定。否则，你可能会收到任意判定，因为你的程序会继续从已关闭的流中读取数据。 每次输出查询或输出答案后，不要忘记换行并刷新输出。否则，你会收到 Idleness Limit Exceeded 判定。为此，请使用： - C++：fflush(stdout) 或 cout.flush() - Java：System.out.flush() - Pascal：flush(output) - Python：stdout.flush() - 其他语言请参见相关文档。 Hack 格式 进行 Hack 时，请按照如下格式输入测试数据。 第一行包含测试用例数 $t$（$1 \le t \le 20$）。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$2 \le n \le 1000$）。 每组测试数据的第二行包含一个括号序列 $s_1 s_2\ldots s_{n}$，其中 $s_i= \texttt{'('}$ 或 $s_i= \texttt{')'}$。 括号序列 $s$ 必须至少包含一个 $\texttt{'('}$ 和一个 $\texttt{')'}$。

在第一个测试用例中，隐藏的括号序列是 $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$。 由 ChatGPT 4.1 翻译