Polish version    English version  
  Historia OI -> VI OI 1998/1999 -> 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
XI OI 2003/2004
X OI 2002/2003
IX OI 2001/2002
VIII OI 2000/2001
VII OI 1999/2000
VI OI 1998/1999
Wyniki III etapu
Wyniki II etapu
Wyniki I etapu
Zadania
Regulamin
Zasady organizacji
Wskazówki
Terminarz
Statystyki
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
VI Olimpiada Informatyczna 1998/99

Zadanie: GRO
Autor: Marcin Kubica
Grotołazi

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?

Zadanie

Napisz program, który:

  • wczytuje z pliku tekstowego gro.in opis jaskini,
  • oblicza największą liczbę grotołazów, którzy mogą odbyć trening jednocześnie,
  • zapisuje wynik w pliku tekstowym .

Wejście

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ą.

Wyjście

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.

Przykład

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 12
opisującego następującą jaskinię:

poprawną odpowiedzią jest plik tekstowy gro.out:

3




Wersja do druku