Giải bài trực tuyến

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à kA, kB thì AB cũng là một biểu thức ngoặc đúng có bậc bằng max(kA, kB).

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.

Example:

INPUT:
6 2
(()){} 

OUTPUT:
4

Giải thích:
1. "(()())"
2. "(())()"
3. "(())[]"
4. "(()){}" 

Ràng buộc:

• n chẵn
• 2*k <= n

Giới hạn:

• Trong 10% test đầu tiên: n, k <= 10.
• Trong 20% test tiếp theo: n <= 20, k <= 5.
• Trong 30% test tiếp theo: n <= 100, k <= 5.
• Trong 40% test còn lại: n, k <= 100.