POLSKI SPOJ

Rozpatrzmy drzewo, które charakteryzuje sie tym, ze każdy wierzchołek z wyjątkiem jednego (korzenia) ma dokładnie jednego ojca i pewna liczbę dzieci. Jeśli wierzchołek nie ma żadnego syna, nazywany jest liściem. Możemy także zdefiniować poddrzewo indukowane przez jeden wierzchołek – drzewo którego ten wierzchołek jest korzeniem, a wszyscy jego synowie i rekurencyjnie kolejni synowie należą do tego drzewa. Każde drzewo można zakodować jako pewna liczbę naturalna na różne sposoby. Jeden z takich sposobów podał Kurt Goedel (funkcja G):

• 1. Jeśli drzewo jest trywialne (zawiera tylko korzeń) wtedy G(T) = 1;
• 2. Niech T będzie drzewem T = korzeń(T₁ . . . T_k) (korzeń jest ojcem T₁ . . . T_k), gdzie T₁ . . . T_k są poddrzewami połączonymi z korzeniem T. Wtedy:

  G(T) = P(G(T₁))*...*P(G(T_k))

  gdzie P(i) oznacza i-ta liczbę pierwsza, a  oznacza zwykłe mnożenie liczb. (Np. P(1) = 2, P(2) = 3, P(3) = 5, P(4) = 7. . . )

Wejście

Wejście składa sie z kolejnych liczb Goedela pooddzielanych spacjami. Ostatnia liczba w tym ciągu jest 0 (dla niego nie odkodowujemy drzewa). Wszystkie te liczby są z przedziału 0..65535.

Wyjście

Specyfikacje wyjścia najlepiej podaje przykład. Korzeniem każdego drzewa będzie :n>, gdzie n jest numerem drzewa, które odkodowujemy. Pozostałe wierzchołki są zakodowane jako . Każde dwa drzewa oddziela linia wolna. Każda krawędź wychodząca z drzewa wychodzi zawsze z > (jak widać w przykładzie) i składa sie z dwóch kresek poziomych i odpowiedniej liczby pionowych (idących prosto w dół od >). Synowie danego wierzchołka muszą być przyłączeni do niego według kolejności niemalejącej.

Przykład

Wejście:
1 3 999 0

Wyjście:
:1>

:3>--<3:2>--<2:1>

:999>--<3:2>--<2:1>
    |
    |--<3:2>--<2:1>
    |
    |--<3:2>--<2:1>
    |
    |--<37:12>--<2:1>
             |
             |--<2:1>
             |
             |--<3:2>--<2:1>