Rotacje na drzewie 2
Limit pamięci: 128 MB
Niniejsze zadanie to trudniejsza wersja zadania
Rotacje na drzewie z II etapu XVIII OI.
Nie wystąpiła ona w samym konkursie.
Ogrodnik Bajtazar zajął się hodowlą rzadkiego drzewa o nazwie Rotatus Informatikus.
Ma ono bardzo ciekawe własności:
-
Drzewo składa się z prostych gałęzi, rozgałęzień i liści.
Wyrastający z ziemi pień drzewa jest również gałęzią.
-
Każda gałąź jest zakończona u góry rozgałęzieniem lub liściem.
-
Z rozgałęzienia na końcu gałęzi wyrastają dokładnie dwie dalsze gałęzie - lewa i prawa.
-
Każdy liść drzewa zawiera jedną liczbę całkowitą z zakresu .
Liczby w liściach nie powtarzają się.
-
Za pomocą pewnych zabiegów ogrodniczych, dla dowolnego rozgałęzienia można
wykonać tzw. rotację, czyli zamienić miejscami lewą i prawą gałąź.
Korona drzewa to ciąg liczb całkowitych, który otrzymujemy,
czytając liczby zawarte w liściach drzewa od lewej do prawej.
Bajtazar pochodzi ze starego miasta Bajtogrodu i jak wszyscy jego mieszkańcy bardzo lubi porządek.
Zastanawia się, jak za pomocą rotacji jak najlepiej uporządkować swoje drzewo.
Uporządkowanie drzewa mierzymy liczbą inwersji zawartych w jego koronie,
tj. dla korony wyznaczamy liczbę takich par , , dla których .
Rys. 1. Oryginalne drzewo (po lewej) o koronie zawiera dwie inwersje.
Po rotacji otrzymujemy drzewo (po prawej) o koronie , które zawiera tylko jedną inwersję.
Każde z tych drzew ma 5 gałęzi.
Napisz program, który wyznaczy minimalną liczbę inwersji zawartych w koronie drzewa,
które można otrzymać za pomocą rotacji wyjściowego drzewa Bajtazara.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita
(), oznaczająca liczbę liści drzewa Bajtazara.
W kolejnych wierszach znajduje się opis drzewa.
Drzewo definiujemy rekurencyjnie:
-
jeśli na końcu pnia (czyli gałęzi, z której wyrasta drzewo) znajduje się liść z liczbą całkowitą (),
to opis drzewa składa się z jednego wiersza zawierającego jedną liczbę całkowitą - ,
-
jeśli na końcu pnia znajduje się rozgałęzienie, to opis drzewa składa się z trzech części:
-
pierwszy wiersz opisu zawiera jedną liczbę ,
-
po tym następuje opis lewego poddrzewa
(tak, jakby lewa gałąź wyrastająca z rozgałęzienia była jego pniem),
-
a następnie opis prawego poddrzewa
(tak, jakby prawa gałąź wyrastająca z rozgałęzienia była jego pniem).
W testach wartych przynajmniej 30% punktów zachodzi dodatkowy warunek
.
Wyjście
W jedynym wierszu standardowego wyjścia należy wypisać jedną liczbę całkowitą:
minimalną liczbę inwersji w koronie drzewa, które można otrzymać za pomocą jakiegoś
ciągu rotacji wyjściowego drzewa.
Przykład
Dla danych wejściowych:
3
0
0
3
1
2
poprawną odpowiedzią jest:
1
Wyjaśnienie do przykładu:
Rysunek 1 ilustruje drzewo z przykładu.
Autorzy zadania: Tomasz Kociumaka, Tomasz Waleń.