COCI '15 Contest 7 #4 Otpor

Points: 12

Time limit: 1.0s

Memory limit: 64M

Problem types

Mirko has been a very good boy, so he got exactly what he wanted for his birthday, a "Young physicist" kit! In the kit, there are $N$ $N$ types of resistors, connecting wires and an ohmmeter. If a resistor is of type $i$ $i$ , it provides a resistance of precisely $R_i$ $R_{i}$ ohms.

As we all know, resistors can be connected in two different ways, in series and parallel. Also, we know that the complete circuit of resistors can be replaced with one resistor of the resistance equal to the equivalent resistance of the circuit. When the circuit is series, it is written in the following way:

Copy

(R1-R2-R3-...-RK)

and the following formula holds:

$\displaystyle R_{ekv} = R_1 + R_2 + R_3 + \dots + R_K$ $R_{e k v} = R_{1} + R_{2} + R_{3} + \dots + R_{K}$

When the circuit is parallel, it is written in the following way:

Copy

(R1|R2|R3|...|RK)

and the following formula holds: $\displaystyle R_{ekv} = \frac{1}{\frac{1}{R_1} + \frac{1}{R_2} + \frac{1}{R_3} + \dots + \frac{1}{R_K}}$ $R_{e k v} = \frac{1}{\frac{1}{R_{1}} + \frac{1}{R_{2}} + \frac{1}{R_{3}} + \dots + \frac{1}{R_{K}}}$

Mirko was excited to bring his new toy to school, where he showed it to all his friends. Unfortunately for him, the teacher also noticed the toy. She quickly connected a circuit and is now asking Mirko to tell her the equivalent resistance of the circuit. Help Mirko and answer the teacher's question!

Input

The first line of input contains the integer $N$ $N$ $(1 \le N \le 9)$ $(1 \leq N \leq 9)$ from the task.

The following line contains $N$ $N$ real numbers $R_i$ $R_{i}$ $(0 < R_i < 100)$ $(0 < R_{i} < 100)$ from the task.

The last line contains the circuit $S$ $S$ , that will not be longer than $100\,000$ $100 000$ characters. $S$ $S$ will only consist of the following characters: R, 1 – 9, (, ), - and |. The number of pairs of brackets will be minimal, and the brackets will be paired properly. Inside of a pair of brackets, there will not be the character - and the character | at the same time. The circuit will only consist of the resistors from the kit and it is possible that not all types of resistors are used, or that one type of resistor is used several times.

Output

The first and only line of output must contain the number from the task. A deviation from the official solution of $\pm 0.00001$ $\pm 0.00001$ is tolerated.

Scoring

In test cases worth $20\%$ $20 %$ of total points, it will hold:

$N = 3$ $N = 3$
$S$ $S$ is going to consist of exactly three resistors, $R_1$ $R_{1}$ , $R_2$ $R_{2}$ and $R_3$ $R_{3}$ , not necessarily in that order

In test cases worth $40\%$ $40 %$ of total points, $S$ $S$ is going to have exactly one pair of brackets.

Sample Input 1

Copy

3
2 3 6
(R1-R2-R3)

Sample Output 1

Copy

11.00000

Sample Input 2

Copy

3
2 3 6
(R1|R2|R3)

Sample Output 2

Copy

1.00000

Sample Input 3

Copy

5
5.0 5.0 5.0 5.0 5.0
((R1-(R2|R3)-(R4|R5))|(R1-(R2|R3)-(R4|R5)))

Sample Output 3

Copy

5.00000

Comments

There are no comments at the moment.