ADBRACK - Thứ tự dãy ngoặc
Giới hạn- Thời gian: 1.0s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
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.
- Người up: ladpro98
- Nguồn bài: Từ một bài của thầy Đỗ Đức Đông