Problem Description

As is well known, resistors can be connected in two ways: series and parallel. All resistors in a circuit can be regarded as the equivalent resistance $R_{ekv}$ of the circuit. A series connection can be written as:

and it satisfies:

A parallel connection can be written as:

and it satisfies:

Now you are given $N$ types of resistors with resistance values $R_i$, and enough wires. Given the connection pattern of these resistors, find the equivalent resistance of the whole circuit.

Input Format

The first line contains an integer $N$.

The second line contains $N$ real numbers $R_i$.

The third line contains a string $S$ that represents the circuit. The string contains only $\texttt R$, $\texttt 1 \sim \texttt 9$, $\texttt ($, $\texttt )$, $\texttt -$, and $\texttt |$. The data guarantees that there will be no mismatched parentheses or illegal situations, and the number of parentheses is minimized. Inside any pair of parentheses, $\texttt -$ and $\texttt |$ will not appear at the same time. The circuit contains only the given $N$ types of resistors, and each type may appear any number of times (including $0$ times).

Output Format

Output the equivalent resistance of the whole circuit. Your answer is considered correct if its absolute or relative error does not exceed $10^{-5}$.

3
2 3 6
(R1-R2-R3)

11.00000

3
2 3 6
(R1|R2|R3)

1.00000

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

5.00000

Hint

Constraints

• For $20\%$ of the testdata, $N=3$ and the circuit contains exactly these three types of resistors.
• For $40\%$ of the testdata, $S$ contains only one pair of parentheses.
• For $100\%$ of the testdata, $1 \le N \le 9$, $0 \lt R_i \lt 100$, $1 \le |S| \le 10^5$.

Hints and Notes

Translated from COCI 2015-2016 #7 Task 4 Otpor.

The score for this problem follows the original COCI settings, with a full score of $120$.

Translated by ChatGPT 5