## COCI '07 Contest 1 #4 Zapis

View as PDF

Points: 15 (partial)
Time limit: 0.6s
Memory limit: 32M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 is a regular bracket-sequence, then , and are also regular bracket-sequences.
• If and are regular bracket-sequences, then is also a regular bracket-sequence. For example, the sequences , and 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 Specification

The first line contains an even integer , the length of the string.

The second line contains the string. Illegible characters are represented by the ? character.

#### Output Specification

Output the number of regular bracket-sequences the string could have read.

#### Sample Input 1

6
()()()

#### Sample Output 1

1

#### Sample Input 2

10
(?([?)]?}?

#### Sample Output 2

3

#### Explanation for Sample Output 2

In the second example, the three matching regular bracket-sequences are , and .

#### Sample Input 3

16
???[???????]????

#### Sample Output 3

92202

• commented on May 6, 2017, 11:18 p.m. edited

Sample input 2 - confusing

How can the output be "(([()]))" when the input contains a "}" character???

Sample input 2: (?([?)]?}?

Also, why is the sample input different length then the output?

• commented on May 6, 2017, 11:31 p.m.

Braces were not escaped; issue has been fixed.