IX Olimpiada Informatyczna 2001/2002
|
Zadanie: min
|
Autor: Piotr Chrząstowski-Wachtel, Wojciech Guzicki
|
Zawody III stopnia, dzień próbny |
Plik źródłowy: | min.??? (np. pas, c, cpp) |
Plik wejściowy: | min.in |
Plik wyjściowy: | min.out |
Działanie odejmowania nie jest łączne, np. (5-2)-1=2, natomiast 5-(2-1)=4, a zatem (5-2)-1<>5-(2-1). Wynika stąd, że wartość wyrażenia postaci 5-2-1 zależy od kolejności wykonywania odejmowań. Przy braku nawiasów przyjmuje się, że wykonujemy działania od lewej strony, czyli wyrażenie 5-2-1 oznacza (5-2)-1. Mamy dane wyrażenie postaci
x1 +/- x2 +/- ... +/- xn,
gdzie +/- oznacza + (plus) lub - (minus), a x1,x2,...,xn oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci
x1-x2-...-xn
tak rozmieścić nawiasy, aby uzyskać wyrażenie równoważne danemu. Dla przykładu, chcąc uzyskać wyrażenie równoważne wyrażeniu
x1-x2-x3+x4+x5-x6+x7
możemy w
x1-x2-x3-x4-x5-x6-x7
rozmieścić nawiasy na przykład tak
((x1-x2)-(x3-x4-x5))-(x6-x7).
Uwaga: Nawiasowania, w których nawiasy nie otaczają żadnej zmiennej lub otaczają tylko jedną zmienną są niedopuszczalne.
Napisz program, który:
W pierwszym wierszu pliku wejściowego min.in zapisana jest jedna liczba całkowita n, 2<=n<=1 000 000. Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych n-1 wierszy jest zapisany jeden znak, + lub -. W i-tym wierszu zapisany jest znak występujący w danym wyrażeniu między xi-1 i xi.
Twój program powinien zapisać w pierwszym wierszu pliku wyjściowego min.out szukany sposób wstawienia nawiasów do wyrażenia x1-x2-...-xn. Należy zapisać tylko nawiasy i minusy (bez odstępów między nimi), pomijając zmienne x1,x2,...,xn. Możesz założyć, że dla danych testowych zawsze istnieje rozwiązanie. Jeśli istnieje wiele możliwych rozwiązań, Twój program powinien zapisać jedno z nich.
Dla pliku wejściowego min.in:
7 - - + + - +
poprawną odpowiedzią jest plik wyjściowy min.out:
((-)-(--))-(-)