CF1906L.Palindromic Parentheses

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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$ .

输入格式

Input consists of two integers $N$ $K$ ( $2 \leq N \leq 2000; 1 \leq K \leq N$ ). $N$ is an even number.

输出格式

If 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.

输入输出样例

输入#1
```
6 4
```
输出#1
```
(())()
```
输入#2
```
6 3
```
输出#2
```
(()())
```
输入#3
```
4 1
```
输出#3
```
-1
```
输入#4
```
14 11
```
输出#4
```
()((())()())()
```

说明/提示

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.

首页