| Author: | A. Klenin | Time limit: | 3 sec | |
| Input file: | Standard input | Memory limit: | 256 Mb | |
| Output file: | Standard output |
For a string of parentheses '(' and ')', let us define shortening as follows. Pick a random pair of characters '(' and ')' such that '(' is to the left of ')' and delete them. Selection probability is distributed uniformly across all possible pairs. Repeat shortening until no suitable pair left.
Given a string of parentheses, your program must calculate the probability of the above process to finish with an empty string.
Input contains a string of parentheses S.
Output must contain a single floating point number — probability with absolute error of no more than 10−7.
1 ≤ |S| ≤ 36
| No. | Standard input | Standard output |
|---|---|---|
| 1 |
|
|
| 2 |
|
|
| 3 |
|
|