K번째 좋은 문자열

시간 제한2초메모리 제한512 MB

요약

괄호 문자열 S가 주어질 때, S의 부분 수열이면서 good string인 서로 다른 문자열을 사전순으로 나열해 K번째를 출력한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 문자열, 조합론
정답자: 아직 제출이 없습니다

문제

좋은 문자열은 다음과 같이 정의한다.

문자열 ()는 좋은 문자열이다.
$S$ 가 좋은 문자열이면 (SS...S)도 좋은 문자열이다. 즉, 같은 좋은 문자열 하나를 한 번 이상 이어 붙인 뒤 전체를 괄호로 감싼 문자열은 좋은 문자열이다.
위의 두 경우를 제외하면 좋은 문자열은 없다.

문자열 $X$ 의 부분 수열은 $X$ 에서 문자를 0개 이상 지워서 얻은 문자열이다.

문자열 $S$ 가 주어진다. $S$ 의 각 문자는 ( 또는 )이다.

$S$ 의 부분 수열 중 좋은 문자열인 것을 서로 다른 것만 모은 집합을 $G$ 라고 하자. $G$ 는 집합이므로 같은 좋은 문자열이 부분 수열로 여러 번 나타나도 $G$ 에는 하나만 들어 있다. 예를 들어 $S$ = (()())이면 $G$ 에는 (), (()), (()())가 들어 있다.

$K$ 가 주어졌을 때 $G$ 에 들어 있는 문자열 중 사전 순으로 $K$ 번째인 문자열을 구하는 프로그램을 작성하시오. 순서는 1부터 센다. 사전 순으로 비교할 때 (는 )보다 앞선다.

입력

첫째 줄에 문자열 $S$ 가 주어진다. $S$ 의 길이는 1 이상 150 이하이다.

둘째 줄에 정수 $K$ 가 주어진다. ( $1 \le K \le 10^9$ )

출력

첫째 줄에 $G$ 에 들어 있는 문자열 중 사전 순으로 $K$ 번째 문자열을 출력한다. 그런 문자열이 없으면 -1을 출력한다.

예제5

예제 1
입력
```
()))((()())
3
```
예상 출력
```
(())
```
예제 2
입력
```
))))))))))))((((((((((
1
```
예상 출력
```
-1
```
예제 3
입력
```
(())(()(()))
1
```
예상 출력
```
(((())))
```
예제 4
입력
```
(())))()((())())
8
```
예상 출력
```
()
```
예제 5
입력
```
(
1000000000
```
예상 출력
```
-1
```