COCI '16 Contest 3 #4 Kvalitetni

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem types

A quality arithmetic expression consists of brackets, numbers and operations of multiplication and addition.

A quality arithmetic expression is defined recursively in the following way:

  • An expression consisting of only one positive real number smaller than or equal to Z_1 is of good quality. For example, if Z_1 = 5, then (4) is a quality expression.
  • If A_1, A_2, \dots, A_k are quality expressions such that 2 \le k \le K and the sum of these expressions is at most Z_k, then the following expressions are of good quality:

\displaystyle (A_1+A_2+\dots+A_k)

\displaystyle (A_1 \times A_2 \times \dots \times A_k)

You are given a quality expression where the numbers are replaced by question marks. Determine the maximal possible value that the expression could have had.

Input Specification

The first line of input contains integer K (2 \le K \le 50).

The second line of input contains integers Z_1, \dots, Z_K, separated by spaces (1 \le Z_1, \dots, Z_K \le 50).

The third line of input contains one quality arithmetic expression in the described format.

An arithmetic expression consists of: ?, *, +, (, ), and its length is at most 1\,000\,000 characters.

Output Specification

You must output the maximal possible value of the expression.

A solution is considered correct if the absolute or relative deviation from the official solution is less than 10^{-3}.

Sample Input 1

2
10 6
((?)+(?))

Sample Output 1

6.00000

Explanation for Sample Output 1

The expression ((3)+(3)) satisfies the conditions, so it is a quality expression, and it is easy to check that 6 is the maximal value.

Sample Input 2

3
2 5 3
(((?)+(?))*(?))

Sample Output 2

6.00000

Explanation for Sample Output 2

The maximum is achieved for, for instance, the expression (((1)+(2))*(2)).

Sample Input 3

3
2 10 6
((?)*(?)*(?))

Sample Output 3

8.000000000

Explanation for Sample Output 3

The maximum is achieved for, for instance, the expression ((2)*(2)*(2)).


Comments

There are no comments at the moment.