Dãy ngoặc

Xem dạng PDF

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~.

  1. Cho biết ~S~ có bao nhiêu phần tử.
  2. 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

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.