시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 64 MB | 9 | 5 | 5 | 55.556% |
A quality arithmetic expression consists of brackets, number and operations of multiplication and addition.
A quality arithmetic expression is defined recursively in the following way:
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.
The first line of input contains integer K (2 ≤ K ≤ 50).
The second line of input contains integers Z1 , …, ZK, separated by space (1 ≤ Z1 , …, ZK ≤ 50).
The third line of input contains one quality arithmetic expression in the described format. Arithmetic expression consists of: ‘?’, ‘*’, ‘+’, ‘(‘, ‘)’, and its length is 1 000 000 characters, at most.
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 .
2 10 6 ((?)+(?))
6.00000
3 2 5 3 (((?)+(?))*(?))
6.00000
3 2 10 6 ((?)*(?)*(?))
8.000000000
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.