Fişierul intrare/ieşire:euler.in, euler.outSursăLista lui Francu
AutorCatalin FrancuAdăugată de
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

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.

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.ineuler.out
7
5 3 6 3 1 3 2 3 5 7 4 7 5
DA
3 3 5 7 0 3 5
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content