In the event of technical difficulties with Szkopuł, please contact us via email at [email protected].
If you would like to talk about tasks, solutions or technical problems, please visit our Discord servers. They are moderated by the community, but members of the support team are also active there.
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.
Napisz program, który:
W pierwszym wierszu standardowego wejścia zapisana jest jedna liczba całkowita , , będąca liczbą komnat (łącznie ze smoczą jamą). Komnaty są ponumerowane od 1 do 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 ). W kolejnych 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 -ta liczba (dla ) jest numerem komnaty, do której prowadzi -ta studnia.
W pierwszym i jedynym wierszu standardowego wyjścia 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.
Dla danych wejściowych:
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
poprawną odpowiedzią jest:
8
Autor zadania: Marcin Kubica.