MREPLBRC - Counting The Way of Bracket Replacement
English | Vietnamese |
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à ([([])]{}).
hide comments
evang12:
2022-01-11 03:29:52
If you are getting wrong answer, it may be due to the unclarity of the problem statement.
|
Added by: | psetter |
Date: | 2009-03-09 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | COCI 1th 07 |