Thứ tự dãy ngoặc

View as PDF

Submit solution

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

Problem source:
Từ một bài của thầy Đỗ Đức Đông
Problem type
Allowed languages
C, C++, Java, Pascal, Python, TEXT

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

Please read the guidelines before commenting.



  • -1
    luandangduc  commented on 27, May, 2021, 13:41

    Trong phần sample cho mình hỏi là các với n, k là 6 và 2 thì [[]][] hoặc 1 số bộ tương tự tại sao lại không được tính?


    • 9
      I_love_Hoang_Yen  commented on 27, May, 2021, 23:29

      Trong sample chỉ in ra 4 bộ có thứ tự từ điển nhỏ nhất (do kết quả test đó bằng 4). Các dãy ngoặc [[]][] hoặc tương tự vẫn hợp lệ, và có thứ tự từ điển lớn hơn.