Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

GOEDEL - Drzewa Goedela

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ń(T1 . . . Tk) (korzeń jest ojcem T1 . . . Tk), gdzie T1 . . . Tk są poddrzewami połączonymi z korzeniem T. Wtedy:

    G(T) = P(G(T1))*...*P(G(Tk))

    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>

Dodane przez:Marcin Sasinowski
Data dodania:2007-11-21
Limit czasu wykonania programu:2.895s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:Eliminacje do MWPZ 2007

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.