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.
Permutacja1
zbioru
jest inwolucją wtedy i tylko wtedy, gdy
dla każdego
.
Wyrażeniem nawiasowym długości będziemy nazywać dowolne słowo długości
składające się wyłącznie ze znaków
'(' oraz ')'.
Wyrażenie nawiasowe jest poprawne, jeśli liczba nawiasów otwierających jest równa liczbie nawiasów zamykających, a w każdym prefiksie tego wyrażenia liczba znaków '(' jest nie mniejsza od liczby znaków ')'.
Powiemy, że permutacja długości
koduje wyrażenie nawiasowe o długości
, jeśli
nawiasy otwierające w wyrażeniu (od lewej do prawej) są na pozycjach
, zaś
zamykające - także od lewej do prawej - na pozycjach
.
W szczególności, w takim przypadku zachodzi
oraz
.
Znamy wartości pewnej permutacji dla niektórych argumentów.
Należy stwierdzić, na ile sposobów można określić pozostałe wartości
, tak by była ona inwolucją i kodowała poprawne wyrażenie nawiasowe.
W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite oraz
(
)
oddzielone pojedynczym odstępem.
W każdym z kolejnych
wierszy znajduje się jedna para liczb całkowitych oddzielonych pojedynczym odstępem;
-ty
spośród tych wierszy zawiera liczby
i
(
), oddzielone pojedynczym odstępem
i oznaczające, że
.
Wszystkie
, jak również wszystkie
, są parami różne.
W pierwszym i jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą:
liczbę permutacji zbioru , które są inwolucjami, kodują poprawne
wyrażenie nawiasowe oraz spełniają podane na wejściu równości.
Dla danych wejściowych:
3 4 1 1 2 2 4 3 6 6
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu:
Jedyna permutacja, która spełnia wymogi zadania, to ,
a koduje ona następujące wyrażenie nawiasowe: (()()).
Autor zadania: Dariusz Leniowski.