Mam takie zadanie:
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−1zależy od kolejności wykonywania odejmowań. Zwykle przy braku nawiasów przyjmuje się, że wykonujemy działania wkolejnoś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), ax1, 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ów-noważ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łnii poprawnie ponawiasowanym jest
•pojedyncza zmienna,
•wyrażenie postaci(w1−w2), w którym w1 i w2 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 konstrukcjepostaci:(),(xi),((···))lubx1−(x2−x3).
Wejście
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita n, (2 <= 5000).Jest to liczba zmiennych w danym wyrażeniu. W każdym z
kolejnychn−1wierszy jest zapisanyjeden znak,+lub−. Wi-tym wierszu zapisany jest znak występujący w danym wyrażeniu międzyxi−1axi.
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 (modulo109), na jakie można
rozstawićn−1par nawiasów wwyrażeniux1−x2−···−xntak, aby jednoznacznie określić kolejność wykonywania odejmowań ijednocześnie uzyskać wyrażenie
równoważne danemu.
Przykład
Dla danych wejściowych: 7 - - + + - +
Zamiast spacji [ENTER],
poprawnym wynikiem jest:3
I nie mam kompletnie pomysłu jak do tego podejść, czy moglibyście mi jakoś pomóc ? :D
Tutaj testuje (mam nadzieje że nie trzeba się będzie logować) https://szkopul.edu.pl/c/archiwum-zadan-k0mpend1x/submit/