괄호 문자열

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

요약

길이 N인 괄호 문자열 중 올바른 괄호 문자열이 아닌 것들을 사전순으로 나열했을 때 K번째 문자열을 조합적 계산으로 구하는 문제입니다.

난이도: 보통10점 중 7점
유형: 조합론, 동적 계획법, 수학, 그리디
정답자: 아직 제출이 없습니다

문제

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

빈 문자열은 괄호 문자열이다.
S가 괄호 문자열이면 (S)도 괄호 문자열이다.
S와 T가 괄호 문자열이면 ST도 괄호 문자열이다.
모든 괄호 문자열은 위의 세 규칙으로만 만들 수 있다.

즉, 괄호 문자열이란 여는 괄호와 닫는 괄호가 올바르게 짝지어진 문자열을 말한다.

이 문제에서는 (와 )로만 이루어져 있지만 괄호 문자열이 아닌 문자열을 다룬다. 그러한 문자열을 괄호가 아닌 문자열이라고 부르자.

길이가 $N$ 인 괄호가 아닌 문자열을 사전순으로 나열했을 때 $K$ 번째(0-인덱스)인 문자열을 출력하는 프로그램을 작성하시오. 그러한 문자열이 없으면 -1을 출력한다. 사전순에서 (는 )보다 앞선다. 사전순으로 가장 앞서는 문자열이 $0$ 번째 문자열이다.

입력

첫째 줄에 두 정수 $N$ 과 $K$ 가 공백으로 구분되어 주어진다.

출력

첫째 줄에 정답 문자열을 출력한다. 조건을 만족하는 문자열이 없으면 -1을 출력한다.

제한

$1 \le N \le 50$
$0 \le K \le 2^N - 1$

예제4

예제 1
입력
```
4 0
```
예상 출력
```
((((
```
예제 2
입력
```
4 4
```
예상 출력
```
())(
```
예제 3
입력
```
6 63
```
예상 출력
```
-1
```
예제 4
입력
```
7 13
```
예상 출력
```
((())()
```