Trójkolorowe drzewa binarne
Limit pamięci: 32 MB
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 ze standardowego wejścia specyfikację drzewa,
- obliczy maksymalną i minimalną liczbę wierzchołków, które można pomalować na zielono,
- wypisze wyniki na standardowe wyjście.
Wejście
Pierwszy i jedyny wiersz standardowego wejścia 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 standardowego wyjścia 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 danych wejściowych:
1122002010
poprawną odpowiedzią jest:
5 2
Autor zadania: Marcin Kubica.
English