powrót

VII Olimpiada Informatyczna 1999/2000

Zadanie: LAB
Autor: Marcin Kubica
Labirynt studni

Zawody II stopnia, dzień drugi 10 lutego 2000
Plik źródłowyLAB.??? (np. PAS,C, CPP)
Plik wykonywalnyLAB.EXE
Plik wejściowyLAB.IN
Plik wyjściowyLAB.OUT

Wewnątrz Bajtogóry znajduje się mityczny labirynt studni. Wejście do labiryntu znajduje się na szczycie góry. Labirynt składa się z wielu komnat. Każda z nich jest w jednym z trzech kolorów: czerwonym, zielonym lub niebieskim. Dwie komnaty tego samego koloru wyglądają identycznie i są nieodróżnialne. W każdej komnacie znajdują się trzy studnie oznaczone numerami 1, 2 i 3. Między komnatami można poruszać się tylko w jeden sposób - wskakując do jednej ze studni spada się (niekoniecznie pionowo) do jednej z komnat położonych niżej. Z komnaty, w której znajduje się wejście do labiryntu można przedostać się w ten sposób do każdej z pozostałych komnat. Wszystkie drogi przez labirynt prowadzą do smoczej jamy znajdującej się na samym jego dnie. Każdemu przejściu przez labirynt odpowiada ciąg numerów studni wybieranych w kolejno odwiedzanych komnatach. Ciąg ten nazywa się planem podróży.

W smoczej jamie żyje Bajtosmok. Legenda głosi, że ten, kto przedstawi Bajtosmokowi dokładny plan labiryntu, otrzyma wielkie skarby. Wszystkich innych Bajtosmok potężnym kopnięciem wyprasza z wnętrza góry.

Śmiałek o imieniu Bajtazar wielokrotnie przemierzał labirynt i opracował jego mapę. Jednak Bajtosmok orzekł, że co prawda wszystkie komnaty znajdują się na mapie, ale wiele komnat jest na niej powtórzonych.

- Ja też - powiedział poklepując Bajtazara po ramieniu - projektując labirynt narysowałem podobny rysunek, ale szybko stwierdziłem, że komnat można zrobić o wiele mniej, a gość poruszający się według dowolnego planu podróży i tak będzie oglądał takie same sekwencje komnat. Pomyślałem trochę i maksymalnie zredukowałem projekt.

Zadanie

Napisz program, który:

Wejście

W pierwszym wierszu pliku tekstowego LAB.IN zapisana jest jedna liczba całkowita n, 2<=n<=6000, będąca liczbą komnat (łącznie ze smoczą jamą). Komnaty są ponumerowane od 1 do n tak, że komnaty o większych numerach znajdują się niżej (komnata, w której znajduje się wejście do labiryntu ma numer 1, a smocza jama ma numer n). W kolejnych n-1 wierszach pliku są opisane komnaty (poza smoczą jamą) oraz studnie prowadzące od nich w dół. W każdym z tych wierszy znajduje się litera, po niej jeden znak odstępu, a następnie trzy liczby całkowite oddzielone pojedynczymi odstępami. Litera oznacza kolor komnaty (C - czerwony, Z - zielony, N - niebieski), a i-ta liczba (dla i=1, 2, 3) jest numerem komnaty, do której prowadzi i-ta studnia.

Wyjście

W pierwszym i jedynym wierszu pliku tekstowego LAB.IN powinna znaleźć się dokładnie jedna liczba całkowita będąca minimalną liczbą komnat w labiryncie (łącznie ze smoczą jamą), przy której podróżnik poruszający się według dowolnego planu obserwuje taką samą sekwencję komnat, jak dla labiryntu opisanego w pliku wejściowym.

Przykład

Dla pliku wejściowego LAB.IN:

11
N 3 5 2
Z 4 5 6
N 7 11 9
N 8 11 10
C 11 9 9
Z 11 9 10
C 11 11 11
C 11 11 11
Z 11 11 11
Z 11 11 11

opisującego następujący labirynt

poprawną odpowiedzią jest plik tekstowy LAB.OUT:

8

powrót