Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

ADBRACK - Thứ tự dãy ngoặc

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.

 


Được gửi lên bởi:Le Anh Duc - A2K42 PBC
Ngày:2015-07-19
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU JS-MONKEY PERL6 PYPY RUST SED
Nguồn bài:Từ một bài của thầy Đỗ Đức Đông

hide comments
2016-02-09 15:23:39 xin đừng quên tôi
THAM KHẢO THUẬT TOÁN VÀ CODE TẠI: http://yeulaptrinh.pw/24/spoj-adbrack/

Last edit: 2016-10-01 07:09:50
2015-09-20 16:19:26 Cường


Last edit: 2015-09-20 16:21:11
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.