MREPLBRC - Counting The Way of Bracket Replacement

English Vietnamese

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/mreplbrc

Dãy ngoặc hợp lệ gồm:

  • Xâu rỗng.
  • A hợp lệ thì (A), [A] và {A} cũng thế.
  • A, B hợp lệ thì AB cũng thế.

Ví dụ : [({})], [](){} và [{}]()[{}] là hợp lệ, [({{([, []({)} và [{}])([{}] không hợp lệ.

Cho một xâu chỉ gồm ( ) { } [ ] và ?. Dấu ? có thể thay thế bằng ngoặc bất kỳ. Tính số cách thay thế mà thu được 1 dẫy ngoặc hợp lệ. Chỉ hiện 5 chữ số cuối cùng.

Input

Dòng đầu là N, độ dài xâu (2 ≤ N ≤ 200), Dòng thứ hai là xâu mô tả.

Output

5 chữ số cuối cùng của dẫy ngoặc hợp lệ thu được. (≤ 5 chữ số thì in ra hết cả kết quả).

Sample

Input:
6
()()()

Output:
1
Input:
10
(?([?)]?}?

Output:
3
Input:
16
???[???????]????

Output:
92202

Ví dụ thứ hai, 3 dãy ngoặc hợp lệ là ({([()])}), ()([()]{}) và ([([])]{}).


Được gửi lên bởi:psetter
Ngày:2009-03-09
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ừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:COCI 1th 07

hide comments
2020-04-02 10:52:42
phải cout như bạn dưới mới AC nhé
2011-06-08 14:31:15 TMTB
test ra số 0 đằng trước nè:
50
([[[???[]?[??][??]?{??({})]??{[]}?{?????}(?()???{?
kq: 00004

Last edit: 2011-06-08 14:32:04
2011-06-07 19:30:44 1212
Cho em xin test mà ra kết quả có mấy số 0 ở đầu được ko ạ và cho em biết trước kq của test đó luôn?
2010-03-30 13:53:48 Trần Hải Ðãng
Đề này dịch không thật tốt, nếu muốn AC cần lưu ý nếu là kết quả gốc là 15 thì in ra 15, nếu là 100015 thì in ra 00015
2009-06-08 02:52:18 Pein
Chỉ hiện 5 chữ số cuối cùng. <- Đề ác quá :D
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.