Bajtonowiec [B]
Limit pamięci: 128 MB
Bajtonowiec to drzewo, na którym rosną bajtony.
Są to rzadkie owoce i można je znaleźć tylko na takich gałęziach,
z których nie wyrastają żadne inne gałęzie.
Wszystkie bajtony rosnące na danej gałęzi mają wyznaczony przedział czasu,
w którym mogą zostać zebrane.
Jeśli zostaną zebrane zbyt wcześnie, będą niedojrzałe, a jeśli za późno - będą zgniłe.
Każdy właściciel bajtonowca zastanawia się, ile minimalnie cięć musi
wykonać, aby zebrać wszystkie bajtony oraz aby każdy zebrany bajton nadawał
się do zjedzenia w chwili zebrania.
Cięcia można wykonywać na każdej gałęzi, u jej początku.
W momencie ścięcia zebrane zostają wszystkie bajtony rosnące bezpośrednio
lub pośrednio na ścinanej gałęzi.
Zakładamy, że w jednostce czasu można wykonać dowolną liczbę
cięć oraz że pień również jest gałęzią.
Wejście
Pierwszy i jedyny wiersz standardowego wejścia zawiera opis bajtonowca,
podany w postaci rekurencyjnej.
Pierwsza liczba oznacza liczbę gałęzi wychodzących z pnia, następnie
znajdują się opisy tych gałęzi.
Opis gałęzi składa się z liczby wychodzących z niej gałęzi, a następnie
opisu tych gałęzi.
Jeśli na gałęzi rosną bajtony, to liczba wychodzących gałęzi jest równa
zeru, a następnie podane są dwie liczby całkowite ,
(),
oznaczające przedział czasu, w którym można zebrać dane bajtony.
Liczba wszystkich gałęzi nie przekracza .
Wyjście
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać jedną liczbę
całkowitą równą minimalnej liczbie cięć, jakie należy wykonać, aby
wszystkie bajtony nadawały się do zjedzenia.
Przykład
Dla danych wejściowych:
2 1 0 3 5 2 0 8 10 1 0 6 9
poprawną odpowiedzią jest:
2
Wyjaśnienie do przykładu: Przykładowy bajtonowiec ma trzy gałęzie, na których
rosną bajtony - przedziały na rysunku to okresy ich zdatności do
spożycia.
Aby zebrać wszystkie bajtony, wystarczą w tym przypadku dwa cięcia:
jedno z nich można wykonać na przykład w chwili 5, a drugie w chwili 8.
Autor zadania: Jacek Tomasiewicz.