Thứ tự dãy ngoặc


Submit solution

Points: 1.67 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

Dãy ngoặc đúng được định nghĩa như sau:

  • Biểu thức rỗng là biểu thức ngoặc đúng có bậc bằng \(0\).
  • Nếu \(A\) là biểu thức ngoặc đúng có bậc bằng \(k\) thì \((A)\), \([A]\), \(\{A\}\) cũng là biểu thức ngoặc đúng có bậc \(k + 1\).
  • Nếu \(A\) và \(B\) tương ứng là hai biểu thức ngoặc đúng có bậc là \(k_A, k_B\) thì \(AB\) cũng là một biểu thức ngoặc đúng có bậc bằng \(max(k_A, k_B)\).

Ví dụ "()[()]" là một biểu thức ngoặc đúng có bậc bằng \(2\).

Với hai số \(n\), \(k\) người ta tiến hành tạo ra tất cả các biểu thức ngoặc đúng có độ dài đúng bằng \(n\) và có bậc không quá \(k\). Sắp xếp các biểu thức ngoặc này theo thứ tự từ điển, chú ý: '(' \(<\) ')' \(<\) '[' \(<\) ']' \(<\) '{' \(<\) '}'.

Yêu cầu: Cho \(n\), \(k\) và \(S\) là một biểu thức ngoặc đúng độ dài \(n\) và có bậc không quá \(k\), hãy tìm thứ tự của \(S\).

Input

  • Dòng đầu chứa hai số nguyên \(n\), \(k\).
  • Dòng thứ hai chứa xâu \(S\).

Output

  • Một dòng duy nhất chứa một số nguyên là thứ tự của biểu thức ngoặc đúng \(S\).

Giới hạn

  • Trong \(10\%\) test đầu tiên: \(n\), \(k \le 10\).
  • Trong \(20\%\) test tiếp theo: \(n \le 20\), \(k \le 5\).
  • Trong \(30\%\) test tiếp theo: \(n \le 100\), \(k \le 5\).
  • Trong \(40\%\) test còn lại: \(n\), \(k \le 100\).
  • \(n\) chẵn
  • \(2 \times k \le n\)

Sample Input

6 2
(()){}

Sample Output

4

Note

  1. "(()())"
  2. "(())()"
  3. "(())[]"
  4. "(()){}"

Comments

There are no comments at the moment.