시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 512 MB | 93 | 31 | 26 | 32.099% |
An n parentheses sequence consists of n (
s and n )
s.
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.
For example, (())
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!
Contest > Google > Google's Coding Competitions > Google APAC 2015 University Graduates Test > Round B APAC Test D2번
Contest > Google > Kick Start > Google Kick Start 2014 > Round B D2번