Một dãy ngoặc đúng được định nghĩa như sau:
() là dãy ngoặc đúng
C là dãy ngoặc đúng nếu C = (A) hoặc C = AB với A, B là các dãy ngoặc đúng
Ví dụ dãy ngoặc đúng: (), (()), ()(), (())()
Ví dụ dãy ngoặc sai: )(, ((((, ()((, )))), )()(
Cho hai số nguyên dương n, k (n <= 3000, k <= 10 ^ 18). Hãy in ra dãy ngoặc đúng thứ k theo thứ tự từ điển.
Input: Gồm một dòng gồm hai số nguyên dương n và k.
Output: Gồm một dòng là dãy ngoặc đúng thứ k theo thứ tự từ điển có độ dài n.
VD1:
Input Output
4 2 ()()
VD2:
Input Output
8 10 ()((()))
Trong ví dụ 1 các dãy ngoặc đúng độ dài 4 theo thứ tự từ điển là :(()), ()().
Ví dụ 2: (((()))),((()())),((())()),((()))(),(()(())),(()()()),(()())(),(())(()),(())()(), ()((())), ()(()()), ()(())(), ()()(()), ()()()().