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
kshubham02:
20170920 07:30:32
Thanks @XilinX


s_jindal00:
20170609 13:35:21
O/p must have leading zeroes if actual answer has zero in last 5 digits. Use long long and apply mod with 10^9 at each step! 

ameya7:
20160925 10:13:38
Last edit: 20160925 12:36:25 

sonu:
20160831 18:42:28
really a nice problem


topke:
20151126 01:12:14
Use long long :D 

Ankit:
20150908 09:25:44
really nice que , but printing format is unnecessary Last edit: 20150908 10:07:15 

Pulkit Singhal:
20150518 09:01:32
Problem Statement Not Visible :(


戚圣凯:
20111204 12:33:31
Tell me why?Always runtime error!!! 

:D:
20100707 19:46:25
I wouldn't say it was boring. A little diversification is welcome and it's not tiresome if programmed right (at least I feel that way). But the description could underline that you need to output leading zeros. It's very easy to miss that when you're accustomed to mod counting. 

Ravi Kiran:
20100531 15:30:41
I agree with Xilinx.

Added by:  ~!(*(@*!@^& 
Date:  20090309 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COCI 1th 07 