Problem hidden
ADBRACK - Thứ tự dãy ngoặc
Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/adbrack
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.
Added by: | Le Anh Duc - A2K42 PBC |
Date: | 2015-07-19 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | Từ một bài của thầy Đỗ Đức Đông |