MREPLBRC  Counting The Way of Bracket Replacement
English  Vietnamese 
A regular bracket sequence is a string of characters consisting only of opening and closing brackets, and satisfying the following conditions:
• An empty string is a regular bracket sequence.
• If A is a regular bracket0sequence, then (A), [A] and {A} are also regular bracket sequences.
• If A and B are regular bracket sequences, then AB is also a regular bracket sequence.
For example, the sequences [({})], [](){} i [{}]()[{}] are regular, but the sequences [({{([, []({)} and [{}])([{}] are not.
Ivica has found a string which looks like it could be a regular bracket sequence. Some of the characters have become smudged and illegible, and could have been any character.
Write a program that calculates how many ways the illegible characters in the string can be replaced by brackets so that the result is a regular bracket sequence. This number can be very large, so output only its last 5 digits.
Input
The first line contains an even integer N (2 <= N <= 200), the length of the string.
The second line contains the string. Illegible characters are represented by the '?' character.
Output
Output the number of regular bracket sequences the string could have read.
Sample
input 6 ()()() output 1 input 10 (?([?)]?}? output 3 input 16 ???[???????]???? output 92202 In the second example, the three matching regular bracket sequences are ({([()])}), ()([()]{}) and ([([])]{}).
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:  0.168s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ERL JSRHINO NODEJS PERL6 VB.NET 
Resource:  COCI 1th 07 