IX Olimpiada Informatyczna 2001/2002
|
Zadanie: naw
|
Autor: Piotr Chrząstowski-Wachtel, Wojciech Guzicki
|
Zawody III stopnia, dzień drugi |
Plik źródłowy: | naw.??? (np. pas, c, cpp) |
Plik wejściowy: | naw.in |
Plik wyjściowy: | naw.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ń. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania w kolejności od lewej do prawej, czyli wyrażenie 5-2-1 jest równoważne wyrażeniu (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 rozstawić n-1 par nawiasów, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu. Na przykład, 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 w następujący sposób:
(((x1-x2)-((x3-x4)-x5))-(x6-x7)).
Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest
Nieformalnie mowiąc, nie interesują nas wyrażenia, w których występują na przykład konstrukcje postaci: (), (xi), ((...)) lub x1-(x2-x3) nie jest w pełni ponawiasowane, ponieważ brakuje zewnętrznych nawiasów.
Napisz program, który:
W pierwszym wierszu pliku tekstowego naw.in zapisana jest jedna liczba całkowita n, 2<=n<=5000. 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 a xi.
Twój program powinien zapisać w pierwszym wierszu pliku tekstowego naw.out jedną liczbę całkowitą równą ilości różnych sposobów (modulo 1 000 000 000), na jakie można rozstawić n-1 par nawiasów w wyrażeniu x1-x2-...-xn tak, aby jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.
Dla pliku wejściowego naw.in:
7 - - + + - +
poprawną odpowiedzią jest plik wyjściowy naw.out:
3