Gửi bài giải
Điểm:
0,38 (OI)
Giới hạn thời gian:
0.38s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Người ta định nghĩa đệ qui dãy ngoặc và cấp của dãy như sau:
- Xâu rỗng được gọi là dãy ngoặc cấp 0.
- Nếu ~S~ là xâu ngoặc cấp ~k~ thì ~(S)~ là xâu ngoặc cấp ~k+1~.
- Nếu ~A, B~ là các dãy ngoặc thì ~S = AB~ là một dãy ngoặc với cấp bằng số lớn hơn trong cấp của ~A~ và ~B~.
Định nghĩa này chỉ áp dụng cho những xâu sinh ra theo qui tắc đệ qui trên.
Cho 2 số nguyên dương ~N~ và ~k~, gọi ~S~ là tập các dãy ngoặc cấp ~k~ độ dài ~N~.
- Cho biết ~S~ có bao nhiêu phần tử.
- Cho một dãy ngoặc thuộc, hãy cho biết thứ tự từ điển của dãy này trong tập ~S~.
Input
- Dòng đầu ghi 2 số ~N~, ~k~ ~\left(N \mbox{ chẵn}, N \le 60, k \le \frac{n}{2}\right)~.
- Dòng hai ghi 1 xâu ngoặc cấp ~k~ độ dài ~N~.
Output
Gồm hai dòng, mỗi dòng trả lời 1 yêu cầu theo thứ tự trên.
Sample Input
6 2
(())()
Sample Output
3
2
Bình luận