Drzewa

Limit pamięci: 32 MB

Drzewa występują bardzo często w informatyce. W odróżnieniu od drzew w naturze drzewa w informatyce rosną do góry nogami: korzeń jest na górze, a liście są na dole. Drzewo składa się z elementów zwanych węzłami. Jeden z węzłów jest korzeniem. Każdy węzeł (oprócz korzenia) ma swojego (dokładnie jednego) ojca . Jeśli węzeł jest ojcem , to jest synem . Węzły nie mające synów nazywamy liśćmi. Synów węzła , ich synów, synów ich synów itd. nazywamy potomkami węzła . Każdy węzeł - oprócz korzenia - jest potomkiem korzenia. Każdy węzeł ma swój poziom. Korzeń ma poziom , a synowie mają poziom o jeden większy od swoich ojców.

Drzewo jest pełnym drzewem binarnym wtedy i tylko wtedy, gdy każdy węzeł ma dokładnie dwóch lub zero synów. W drzewach binarnych rozróżniamy lewego i prawego syna.

Powyższy rysunek przedstawia przykładowe pełne drzewo binarne. Węzły tego drzewa są ponumerowane w specjalnej kolejności (nazywanej w literaturze angielskiej preorder). W kolejności tej korzeń ma numer , ojciec poprzedza synów, a lewy syn i dowolny jego potomek ma numer mniejszy niż prawy syn i każdy jego potomek.

Jest wiele sposobów zapisu pełnych drzew binarnych z taką numeracją węzłów. Oto trzy z nich.

Zapis genealogiczny
Jest to ciąg liczb. Pierwszy element ciągu jest równy (zero), zaś dla , -ty wyraz ciągu jest numerem ojca węzła .

Zapis nawiasowy
Każdemu węzłowi przyporządkowujemy napis złożony z nawiasów. Liściom przyporządkowujemy napis . Każdemu z pozostałych węzłów w przyporządkowujemy napis postaci: , gdzie i oznaczają napisy przyporządkowane odpowiednio lewemu i prawemu synowi . Napis przyporządkowany korzeniowi jest zapisem nawiasowym drzewa.

Zapis poziomowy
Jest to ciąg poziomów kolejnych liści drzewa (zgodnie z przyjętą numeracją).

Drzewo przedstawione na rysunku można opisać następująco:

Zadanie

Napisz program, który wczytuje ze standardowego wejścia ciąg liczb i bada, czy jest on zapisem poziomowym pełnego drzewa binarnego. Jeśli nie jest, to zapisuje w standardowym wyjściu jeden wyraz NIE, a jeśli jest, to znajduje dwa inne zapisy tego drzewa (genealogiczny i nawiasowy) i zapisuje je w standardowym wyjściu.

Wejście

W pierwszym wierszu standardowego wejścia zapisana jest dodatnia liczba wyrazów ciągu (nie większa niż 2500). W drugim wierszu zapisane są kolejne wyrazy ciągu oddzielone pojedynczymi odstępami. Liczby w standardowym wejściu są zapisane poprawnie. Twój program nie musi tego sprawdzać.

Wyjście

Standardowe wyjście powinno zawierać:

• tylko jeden wyraz NIE
• albo:
  • w pierwszym wierszu kolejne wyrazy zapisu genealogicznego oddzielone pojedynczymi odstępami,
  • w drugim wierszu zapis nawiasowy, tzn. ciąg nawiasów lewych i prawych bez odstępów między nimi.

Przykłady

Dla danych wejściowych:

5
2 2 3 3 2 

poprawną odpowiedzią jest:

0 1 2 2 1 5 6 6 5 
((()())((()())()))

Dla danych wejściowych:

4
1 2 2 3 

poprawną odpowiedzią jest:

NIE

Autor zadania: Wojciech Rytter.