Bankomat
Limit pamięci: 32 MB
Bajtocki Bank Bitowy (w skrócie BBB) ma największą w
Bajtocji sieć bankomatów.
Klienci BBB wypłacają pieniądze z bankomatów na podstawie
karty bankomatowej i 4-cyfrowego kodu PIN.
Niedawno, w celu zwiększenia bezpieczeństwa swoich klientów,
BBB zainstalował przy każdym bankomacie kamerę.
Kamery przesyłają rejestrowany obraz do BBB drogą radiową.
Niestety, sygnał wysyłany przez kamery jest przechwytywany przez
szajkę złodziejaszków komputerowych.
Złodziejaszkowie starają się odkryć 4-cyfrowe kody PIN klientów BBB,
którym następnie kradną karty bankomatowe.
Wiedząc o tym, klienci BBB, wprowadzając PIN i przesuwając palec nad
klawiaturą, starają się wykonywać nadmiarowe ruchy.
Kamera nie jest w stanie wychwycić naciskania klawiszy,
rejestruje jedynie przesunięcia palca.
Tak więc, jednoznaczne wyznaczenie wprowadzanego kodu PIN jest
zazwyczaj niemożliwe.
Przykładowo, klient przesuwający swój palec najpierw nad klawiszem 1,
a potem 5, mógł wprowadzić następujące kody PIN:
1111, 1115, 1155, 1555 lub 5555.
Zdesperowani złodziejaszkowie gromadzą nagrania z kamer, licząc na to,
że być może na podstawie wielu nagrań tego samego klienta będą w stanie
wyznaczyć wprowadzany przez niego PIN, lub choćby ograniczyć liczbę
możliwych kodów.
Zebrawszy sekwencje wprowadzane przez pewnego bogatego klienta BBB,
złożyli Ci propozycję "nie do odrzucenia".
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis zarejestrowanych
sekwencji ruchów palca, jakie klient banku wykonywał
wprowadzając swój PIN,
-
wyznaczy liczbę różnych kodów PIN, jakie może mieć klient
(czyli liczbę tych 4-cyfrowych kodów PIN, które mogły być
wprowadzone do bankomatu przy wykonywaniu zadanych sekwencji ruchów
palca),
-
wypisze znalezione rozwiązanie na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera jedną dodatnią liczbę całkowitą
równą liczbie zarejestrowanych scen wprowadzania kodu PIN przez klienta,
.
W kolejnych wierszach znajdują się opisy tych scen, po jednej w
wierszu.
Opis każdej sceny składa się z dwóch dodatnich liczb całkowitych
oddzielonych pojedynczym odstępem.
Pierwsza z tych liczb, , to długość sekwencji ruchów,
.
Druga z tych liczb to -cyfrowa liczba, której kolejne cyfry
reprezentują kolejne klawisze, nad którymi klient przesuwał palec.
Łączna długość wszystkich sekwencji nie przekracza .
Wyjście
W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna
dodatnia liczba całkowita równa liczbie możliwych kodów PIN
klienta.
Przykład
Dla danych wejściowych:
2
3 123
3 234
poprawną odpowiedzią jest:
5
Autor zadania: Piotr Stańczyk.