W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
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
Napisz program, który:
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 .
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.
Dla danych wejściowych:
7 - - + + - +
poprawną odpowiedzią jest:
3
Autorzy zadania: Piotr Chrząstowski, Wojciech Guzicki.