| Fişierul intrare/ieşire: | euler.in, euler.out | Sursă | Lista lui Francu |
| Autor | Catalin Francu | Adăugată de | |
| Timp execuţie pe test | 0.125 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   2/5 |
Vezi solutiile trimise | Statistici
Euler
 Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema! |
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.
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.
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.
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.
Restrictii
- 1 ≤ N ≤ 262 144
- Numarul de numere date nu depaseste 524 288
Exemplu
| euler.in | euler.out |
|---|---|
| 7 5 3 6 3 1 3 2 3 5 7 4 7 5 | DA 3 3 5 7 0 3 5 |
