|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|5 초||512 MB||39||12||12||30.769%|
An n parentheses sequence consists of n
(s and n
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses
() until it becomes empty.
(()) is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes
() then you can make it empty.
)()( is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes
)( and you cannot erase any more.
Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.
For example, here are all valid 3 parentheses sequences in lexicographical order:
((())) (()()) (())() ()(()) ()()()
The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case consisting of 2 integers, n and k.
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the k-th smallest parentheses sequence in all valid n parentheses sequences. Output "Doesn't Exist!" when there are less than k different n parentheses sequences.
3 2 2 3 4 3 6
Case #1: ()() Case #2: ()(()) Case #3: Doesn't Exist!