Submit solution
Points:
1.82 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Problem source:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Xét định nghĩa ~1~ dãy ngoặc đúng:
- Nếu ~A~ không có ký tự nào thì ~A~ là dãy ngoặc đúng
- Neu ~A~ là dãy ngoặc đúng thì ~(A)~ là dãy ngoặc đúng
- - Nếu ~A~ và ~B~ là ~2~ dãy ngoặc đúng thì AB là dãy ngoặc đúng
Ta gọi bậc của dãy ngoặc đúng ~S~ là hàm ~deg(S)~. Gọi ~R~ là dãy ngoặc thu được bằng cách xóa đi ~N~ div ~2~ ký tự đầu và ~N~ div ~2~ ký tự cuối của ~S~, trong đó ~2 \times N~ là độ dài của ~S~. Ta có công thức đệ quy tính ~deg(S)~ như sau:
- Nếu ~R~ không phải dãy ngoặc đúng thì ~deg(S)~ ~= 1~
- Nếu ~R~ là dãy ngoặc đúng thì ~deg(S)~ ~=~ ~deg(R)~ ~+ 1~
Ví dụ dãy (()()) có bậc là ~2~, dãy ()(()) có bậc là ~1~, dãy (()) có bậc lớn vô cùng (áp dụng vô hạn lần công thức đệ quy trên).
Yêu cầu: Xét cách dãy ngoặc có độ dài ~2 \times N~ và bậc ~P~, hãy in ra dãy ngoặc có thứ tự từ điển thứ ~K~.
Input
Gồm một dòng duy nhất ghi ra ~3~ số ~N~, ~P~, ~K~.
Output
Gồm một dòng duy nhất ghi ra dãy ngoặc tìm được.
Giới hạn
- ~1 \le N \le 40~, ~1 \le P \le 6~, ~K~ nguyên dương không vượt quá ~10^{18}~ và không vượt quá số lượng dãy ngoặc độ dài ~2 \times N~ bậc ~P~.
- Ký tự '(' có thứ tự từ điển nhỏ hơn ký tự ')'
Sample Input
3 1 2
Sample Output
()(())
Note
Có ~3~ dãy ngoặc độ dài ~6~ và bậc ~1~ là: (())(), ()(()), ()()().
Comments