Dãy ngoặc

View as PDF

Submit solution


Points: 0.38 (partial)
Time limit: 0.38s
Memory limit: 512M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.