Nawiasy
Limit pamięci: 32 MB
Działanie odejmowania nie jest łączne, np. , natomiast ,
a zatem . Wynika stąd, że wartość wyrażenia postaci
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
jest równoważne wyrażeniu .
Mamy dane wyrażenie postaci:
gdzie oznacza (plus) lub (minus), a
oznaczają (parami) różne zmienne. Chcemy w wyrażeniu postaci:
tak rozstawić 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:
możemy w:
rozmieścić nawiasy w następujący sposób:
.
Uwaga: Interesują nas tylko wyrażenia w pełni i poprawnie ponawiasowane. Wyrażeniem w pełni i poprawnie ponawiasowanym jest
- albo pojedyncza zmienna,
- albo wyrażenie postaci , w którym i , to
w pełni i poprawnie ponawiasowane wyrażenia.
Nieformanie mowiąc, nie interesują nas wyrażenia, w których występują na przykład konstrukcje
postaci:
,
,
lub
nie jest w pełni ponawiasowane, ponieważ brakuje zewnętrznych nawiasów.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis danego wyrażenia postaci ,
- obliczy na ile różnych sposobów (modulo ) można rozstawić
par nawiasów w wyrażeniu tak, aby
jednoznacznie określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu,
- wypisze wynik na standardowe wyjście.
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita ,
. Jest to liczba zmiennych w danym wyrażeniu. W każdym z kolejnych
wierszy jest zapisany jeden znak, lub . W -tym
wierszu zapisany jest znak występujący w danym wyrażeniu między a .
Wyjście
Twój program powinien zapisać w pierwszym wierszu standardowego wyjścia jedną liczbę całkowitą
równą ilości różnych sposobów (modulo ), na jakie można rozstawić
par nawiasów w wyrażeniu tak, aby jednoznacznie
określić kolejność wykonywania odejmowań i jednocześnie uzyskać wyrażenie równoważne danemu.
Przykład
Dla danych wejściowych:
7
-
-
+
+
-
+
poprawną odpowiedzią jest:
3
Autorzy zadania: Piotr Chrząstowski, Wojciech Guzicki.