Polish version    English version  
  Historia OI -> XII OI 2004/2005 -> Zadania


 Aktualności
 O olimpiadzie
 Komitety
 XVIII OI 2010/2011
 Historia OI
XVII OI 2009/2010
XVI OI 2008/2009
XV OI 2007/2008
XIV OI 2006/2007
XIII OI 2005/2006
XII OI 2004/2005
Terminarz
Zadania
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
II Etap
III Etap
Przepisy
Dla zawodników
Przydatne zasoby
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
V OI 1997/1998
IV OI 1996/1997
III OI 1995/1996
II OI 1994/1995
I OI 1993/1994
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
XII Olimpiada Informatyczna 2004/2005

Zadanie: ban

Bankomat

Zawody I stopnia  
Plik źródłowy: ban.xxx (xxx=pas,c,cpp)
Limit pamięci: 32 MB

Alternatywne formaty: PostScript | PDF

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ą n równą liczbie zarejestrowanych scen wprowadzania kodu PIN przez klienta, 1 <= n <= 1000. W kolejnych n 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, t, to długość sekwencji ruchów, 1 <= t <= 10.000. Druga z tych liczb to t-cyfrowa liczba, której kolejne cyfry reprezentują kolejne klawisze, nad którymi klient przesuwał palec. Łączna długość wszystkich sekwencji nie przekracza 1.000.000.

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

prawidłową odpowiedzią jest:

5



Wersja do druku