IX Olimpiada Informatyczna 2001/2002
|
Task: naw
|
Author: Piotr Chrz±stowski-Wachtel, Wojciech Guzicki
|
III stage contest |
The operation of subtraction is not associative, e.g. (5-2)-1=2, but 5-(2-1)=4, therefore (5-2)-1<>5-(2-1). It implies that the value of the expression of the form 5-2-1 depends on the order of performing subtractions. Usually in lack of brackets we assume that the operations are performed from left to right, i.e. the expression 5-2-1 is equivalent to the expression (5-2)-1.
We are given an expression of the form
x1 +/- x2 +/- ... +/- xn,
where each +/- denotes either + (plus) or - (minus), and x1,x2,...,xn denote (pairwise) distinct variables. In an expression of the form
x1-x2-...-xn
we want to insert n-1 pairs of brackets to unambiguously determine the order of performing subtractions and, in the same time, to obtain an expression equivalent to the given one. For example, if we want to obtain an expression equivalent to the expression
x1-x2-x3+x4+x5-x6+x7
we may insert brackets into
x1-x2-x3-x4-x5-x6-x7
as follows:
(((x1-x2)-((x3-x4)-x5))-(x6-x7)).
Note: We are interested only in fully and correctly bracketed expressions. An expression is fully and correctly bracketed when it is
Informally speaking, we are not interested in expressions containing spare brackets like: (), (xi), ((...)). But the expression x1-(x2-x3) is not fully bracketed because it lacks the outermost brackets.
7 - - + + - +the correct answer is in the following output file naw.out:
3