In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you are familiar with IRC chat, the support team is also reachable on PIRC network (irc.pirc.pl
) in #szkopul
channel. If you are not, just use email.
Please do not ask us things like "how to solve task XYZ?".
Please remember that the support team has to sleep sometimes or go to work in real life.
To zadanie pojawiło się równolegle na finale IX OI. Polecamy wysyłać rozwiązania do tamtego zadania, to zostanie wkrótce usunięte z serwisu.
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