powrót

VI Olimpiada Informatyczna 1998/99

Zadanie: TRO
Autor:
Trókolorowe drzewa binarne

Etap III, dzień próbny 20 kwietnia 1999
Plik źródłowyTRO.??? (np. PAS,C, CPP)
Plik wykonywalnyTRO.EXE
Plik wejściowyTRO.IN
Plik wyjściowyTRO.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:

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

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

Zadanie

Napisz program, który:

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
poprawna odpowiedzia jest plik wyjściowy TRO.OUT:
5 2

powrót