Dãy ngoặc bậc P

View as PDF

Submit solution

Points: 1.82 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem source:
Thi vòng 2 - 2008
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

Please read the guidelines before commenting.


There are no comments at the moment.