310903: CF1906L. Palindromic Parentheses
Description
Construct a parentheses sequence consisting of $N$ characters such that it is balanced and the length of its longest palindromic subsequence (LPS) is exactly $K$. Determine whether such a construction is possible. If there are several possible sequences, construct any of them.
A parentheses sequence consists of only character ( and ). A parentheses sequence is balanced if each character ( has a corresponding character ) and the pairs of parentheses are properly nested. For example, (), (()), (())(), and ((())()) are balanced. However, )(, ((), and ()) are not balanced.
A sequence is palindromic if it reads the same backwards as forwards. For example, ((, ), ())(, and (()(( are palindromic. However, (), )(, and (()) are not palindromic.
A subsequence can be derived from another sequence by removing zero or more characters without changing the order of the remaining characters. For example, (, ))), ())(, and (())() are subsequence of (())(). However, )(( and ((())) are not subsequence of (())().
The longest palindromic subsequence (LPS) of a sequence is a subsequence with the maximum number of characters, derived from that sequence and it is palindromic. For example, the LPS of sequence (())() is ())(, which can be obtained by removing the second and sixth characters. Therefore, the length of the LPS of (())() is $4$.
InputInput consists of two integers $N$ $K$ ($2 \leq N \leq 2000; 1 \leq K \leq N$). $N$ is an even number.
OutputIf there is no such parentheses sequence such that it is balanced and the length of its LPS is exactly $K$, then output -1.
Otherwise, output a string of $N$ characters, representing the parentheses sequence. If there are several possible answers, output any of them.
ExamplesInput6 4Output
(())()Input
6 3Output
(()())Input
4 1Output
-1Input
14 11Output
()((())()())()Note
Explanation for the sample input/output #2
The LPS of (()()) is either ((( by removing all ) characters, or ))) by removing all ( characters.
The output ((())) also satisfies the requirements.
Explanation for the sample input/output #3
The only possible balanced parentheses sequences are (()) and ()(). The length of the LPS of (()) and ()() are $2$ and $3$, respectively.
Explanation for the sample input/output #4
The LPS of ()((())()())() is )())()())(), which can be obtained by removing the first, fourth, and fifth characters.
Output
构造一个由N个字符组成的括号序列，使其**平衡**，并且其**最长回文子序列（LPS）**的长度恰好为K。确定是否可以构建这样的序列。如果有多个可能的序列，则构建其中任何一个。
一个括号序列只包含字符 `(` 和 `)`。如果每个开括号 `(` 都有一个对应的闭括号 `)` 并且括号对正确嵌套，则该括号序列是**平衡**的。例如，`()`、`(())`、`(())()` 和 `((())())` 是平衡的。然而，`())`、`(()` 和 `())` 不是平衡的。
如果序列从前向后和从后向前读取相同，则该序列是**回文**的。例如，`((`、`)`、`())(` 和 `(()((` 是回文的。然而，`()`、`())` 和 `(())` 不是回文的。
**子序列**可以通过删除零个或多个字符而不改变剩余字符的顺序，从另一个序列派生出来。例如，`(`、`)))`、`())(` 和 `(())()` 是 `(())()` 的子序列。然而，`)((` 和 `((()))` 不是 `(())()` 的子序列。
序列的**最长回文子序列（LPS）**是具有最大字符数的、派生自该序列并且是回文的子序列。例如，序列 `(())()` 的 LPS 是 `())(`，这可以通过删除第二个和第六个字符获得。因此，`(())()` 的 LPS 长度为 4。
**输入输出数据格式：**
**输入：**
输入包含两个整数 N 和 K（2 ≤ N ≤ 2000; 1 ≤ K ≤ N）。N 是一个偶数。
**输出：**
如果没有这样的括号序列，使其平衡且其 LPS 的长度正好为 K，则输出 `-1`。
否则，输出一个包含 N 个字符的字符串，表示括号序列。如果有多个可能的答案，输出其中任何一个。**题目大意：** 构造一个由N个字符组成的括号序列，使其**平衡**，并且其**最长回文子序列（LPS）**的长度恰好为K。确定是否可以构建这样的序列。如果有多个可能的序列，则构建其中任何一个。 一个括号序列只包含字符 `(` 和 `)`。如果每个开括号 `(` 都有一个对应的闭括号 `)` 并且括号对正确嵌套，则该括号序列是**平衡**的。例如，`()`、`(())`、`(())()` 和 `((())())` 是平衡的。然而，`())`、`(()` 和 `())` 不是平衡的。 如果序列从前向后和从后向前读取相同，则该序列是**回文**的。例如，`((`、`)`、`())(` 和 `(()((` 是回文的。然而，`()`、`())` 和 `(())` 不是回文的。 **子序列**可以通过删除零个或多个字符而不改变剩余字符的顺序，从另一个序列派生出来。例如，`(`、`)))`、`())(` 和 `(())()` 是 `(())()` 的子序列。然而，`)((` 和 `((()))` 不是 `(())()` 的子序列。 序列的**最长回文子序列（LPS）**是具有最大字符数的、派生自该序列并且是回文的子序列。例如，序列 `(())()` 的 LPS 是 `())(`，这可以通过删除第二个和第六个字符获得。因此，`(())()` 的 LPS 长度为 4。 **输入输出数据格式：** **输入：** 输入包含两个整数 N 和 K（2 ≤ N ≤ 2000; 1 ≤ K ≤ N）。N 是一个偶数。 **输出：** 如果没有这样的括号序列，使其平衡且其 LPS 的长度正好为 K，则输出 `-1`。 否则，输出一个包含 N 个字符的字符串，表示括号序列。如果有多个可能的答案，输出其中任何一个。