VI Olimpiada Informatyczna 1998/99
|
Zadanie: GRO
|
Autor: Marcin Kubica
|
Zawody II stopnia, dzień pierwszy | 10 lutego 1999 |
Plik źródłowy: | GRO.??? (np. pas, c, cpp) |
Plik wykonywalny: | GRO.exe |
Plik wejściowy: | GRO.in |
Plik wyjściowy: | GRO.out |
Drużyna grotołazów organizuje trening w największej jaskini Bajtogór. Trening polega na przebyciu drogi od komory leżącej najwyżej, do komory leżącej najniżej. Grotołazi mogą posuwać się tylko w dół, tzn. kolejne odwiedzane komory muszą leżeć coraz niżej. Dodatkowo każdy z nich ma wyjść z najwyższej komory innym korytarzem oraz każdy z nich ma wejść do najniższej komory innym korytarzem. Pozostałe korytarze grotołazi mogą pokonywać wspólnie. Ilu grotołazów może odbyć trening jednocześnie?
Napisz program, który:
W pierwszym wierszu pliku tekstowego gro.in jest zapisana jedna liczba całkowita n (2<=n<=200), równa liczbie komór w jaskini. Komory są ponumerowane liczbami do 1 do n w taki sposób, że komora z większym numerem leży niżej od komory z numerem mniejszym. (Najwyższa komora ma numer 1, a najniższa n.) W wierszach o numerach 2,3,...,n są opisane korytarze wychodzące z kolejnych komór 1,2,...,n-1, do komór o wyższych numerach (w wierszu o numerze i znajduje się opis korytarzy wychodzących z komory o numerze i-1). Każdy z tych wierszy zawiera ciąg nieujemnych liczb całkowitych pooddzielanych pojedynczymi odstępami. Pierwsza liczba w wierszu, m, 0<=m<=(n-i+1), jest liczbą korytarzy prowadzących z komory do komór o wyższych numerach, natomiast kolejne m liczb to numery komór, do których te korytarze prowadzą.
W jedynym wierszu pliku gro.out Twój program powinien zapisać jedną liczbę całkowitą, równą maksymalnej liczbie grotołazów mogących wziąć jednocześnie udział w treningu.
Dla pliku wejściowego gro.in:
12 4 3 4 2 5 1 8 2 9 7 2 6 11 1 8 2 9 10 2 10 11 1 12 2 10 12 1 12 1 12opisującego następującą jaskinię:
poprawną odpowiedzią jest plik tekstowy gro.out:
3