Polish version    English version  
  O olimpiadzie -> Zadania


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 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: TRO
Autor: Marcin Kubica
Trójkolorowe drzewa binarne

Etap III, dzień próbny 20 kwietnia 1999
Plik źródłowy: TRO.??? (np. pas, c, cpp)
Plik wykonywalny: TRO.exe
Plik wejściowy: TRO.in
Plik wyjściowy: TRO.out

Drzewo składa się z wierzchołka, do którego podczepiono zero, jedno lub dwa poddrzewa, zwane dziećmi.

Specyfikacją drzewa nazywamy ciąg cyfr. Jeżeli drzewo składa się z wierzchołka, do którego podczepiono:

  • zero dzieci, to jego specyfikacja jest ciągiem jednoelementowym, którego jedynym elementem jest cyfra `0';
  • jedno dziecko, to jego specyfikacja jest ciągiem rozpoczynającym się od cyfry `1'; po której następuje specyfikacja dziecka.
  • dwoje dzieci, to jego specyfikacja jest ciągiem rozpoczynającym się od cyfry `2', po której następuje najpierw specyfikacja jednego, a potem drugiego dziecka.

Każdy wierzchołek drzewa trzeba pomalować na czerwono, zielono lub niebiesko. Należy jednak trzymać się dwóch zasad:

  • wierzchołek i jego dziecko nie mogą być pomalowane na ten sam kolor,
  • jeżeli wierzchołek ma dwoje dzieci, to muszą one być pomalowane różnymi kolorami.

Ile wierzchołków można pomalować na zielono?

Zadanie

Napisz program, który:

  • wczyta z pliku tekstowego TRO.IN specyfikację drzewa,
  • obliczy maksymalną i minimalną liczbę wierzchołków, które można pomalować na zielono,
  • zapisze wyniki w pliku tekstowym TRO.OUT.

Wejście

Pierwszy i jedyny wiersz pliku wejściowego TRO.IN zawiera słowo o długości nie przekraczającej 10000 znaków, będącą specyfikacją pewnego drzewa.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego TRO.OUT dokładnie dwie liczby całkowite oddzielone pojedynczym odstępem, odpowiednio maksymalną i minimalną liczbą wierzchołków, które można pomalować na zielono.

Przykład

Dla pliku wejściowego TRO.IN:
1122002010
poprawną odpowiedzią jest plik wyjściowy TRO.OUT:
5 2



Wersja do druku