euler

Euler

== include(page="template/taskheader" task_id="euler") ==
 
Poveste ...
 
h2. Cerinta
 
...
 
h2. Restrictii
 
...
 
h2. Date de intrare
 
...
 
h2. Date de iesire
 
...
 
h2. Exemplu
 
| euler.in | euler.out |
| linia1
linia2
linia3
| linia1
linia2
|
 
== include(page="template/taskfooter" task_id="euler") ==

==Include(page="template/taskheader" task_id="euler")==
==Include(page="template/raw")==
 
euler
 
Fie un arbore general cu radacina fixata. Arborele are N noduri numerotate de la 1 la N. O parcurgere euler a acestui arbore se face astfel: se tipareste radacina arborelui curent iar pentru fiecare din fii radacinii se afiseaza parcurgerea euler a subarborelui respectiv dupa care se afiseaza si radacina. De exemplu, pentru arborele cu 7 noduri, cu radacina in nodul 5 si cu lista de muchii (5 3), (5 7), (3 6), (3 1), (3 2), (7 4), parcurgerea euler este 5 3 6 3 1 3 2 3 5 7 4 7 5.
 
h2. Cerinta
 
Problema cere ca, dandu-se un numar N si o succesiune de numere, sa se spuna daca succesiunea reprezinta o parcurgere euler corecta a unui arbore cu N noduri si, in caz afirmativ, sa se reconstituie arborele.
 
h2. Date de Intrare
 
In fisierul de intrare euler.in se va afla pe prima linie numarul N, iar pe a doua linie o succesiunea de numere naturale cuprinse intre 1 si N. Numarul de numere este necunoscut.
 
h2. Date de Iesire
 
Fisierul de iesire euler.out va contine pe prima linie unul din mesajele DA sau NU, in functie daca secventa de numere este sau nu o secventa euler a unui arbore cu N noduri. Daca raspunsul este DA, a doua linie va contine N numere naturale, unde al i-lea numar va fi tatal nodului i. Daca nodul i este radacina, se va afisa pe pozitia corespunzatoare 0.
 
h2. Restrictii
 
o 1 <= N <= 262 144
o Numarul de numere date nu depaseste 524 288
 
h2. Exemplu
 
 
 
euler.in euler.out
7 DA
 
5 3 6 3 1 3 2 3 5 7 4 7 5 3 3 5 7 0 3 5
 
 
==Include(page="template/taskfooter" task_id="euler")==