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.
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.