IX Olimpiada Informatyczna 2001/2002
|
Task: min
|
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. In lack of brackets we assume that the operations are performed from left to right, i.e. the expression 5-2-1 denotes (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 brackets in such a way as 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: Brackets that surround none or only one variable are not allowed.
7 - - + + - +a correct answer is in the following output file min.out:
((-)-(--))-(-)