Diferente pentru problema/planeta intre reviziile #7 si #1

Diferente intre titluri:

Planeta
planeta

Diferente intre continut:

== include(page="template/taskheader" task_id="planeta") ==
Satula de atatea Stele, Miruna s-a mutat pe Planeta Moldova. Aici ea a auzit pentru prima data de notiunile de _arbore binar_ si _arbore binar de cautare_. Un _arbore binar_ este definit astfel in mod recursiv:
 
* este un arbore fara niciun nod.
* este un arbore format dintr-un nod special numit _radacina_ si alti doi _arbori binari_, numiti _subarborele stang_ si _subarborele drept_ ai _radacinii_.
 
Fiecare nod al unui arbore binar cu $N$ noduri va contine un numar intre $1$ si $N$. Vom considera ca un _arbore binar_ este _arbore binar de cautare_ daca sunt indeplinitie urmatoarele conditii _pentru fiecare nod al arborelui_:
 
* toate valorile din _subarborele stang_ sunt _mai mici strict_ decat valoarea din nod
* toate valorile din _subarborele drept_ sunt _mai mari strict_ decat valoarea din nod
 
Mai jos avem un exemplu de arbore binar de cautare cu sase noduri:
 
!problema/planeta?BST.JPG 70%!
 
_Parcurgerea in pre-ordine_ a unui _arbore binar de cautare_ este un sir de numere care se obtine astfel:
 
* parcurgerea in pre-ordine a unui arbore fara niciun nod este un sir vid
* parcurgerea in pre-ordine a unui arbore nevid se obtine astfel: fie $L$ sirul reprezentand parcurgerea in pre-ordine a subarborelui stang al radacinii, $V$ valoarea din radacina si $R$ sirul reprezentand parcurgerea in pre-ordine a subarborelui drept al radacinii. Parcurgerea in pre-ordine a arborelui se obtine concatenand $V$, $L$ si $R$.
 
Pentru exemplul de mai sus _parcurgerea in pre-ordine_ este sirul: $3 1 2 4 6 5$.
 
Miruna analizeaza toti _arborii binari de cautare_ cu $N$ noduri care contin numerele $1, 2, ..., N$ si ii parcurge in _pre-ordine_. Apoi sorteaza sirurile care reprezinta parcurgerile lexicografic. Voi va trebui sa ii raspundeti Mirunei la o intrebare foarte simpla: care este al $K$-lea sir in ordine lexicografica?
Poveste şi cerinţă...
h2. Date de intrare
Pe prima liniei a fisierului de intrare $planeta.in$ contine doua numere intregi $N$ si $K$, avand semnificatia din enunt.
Fişierul de intrare $planeta.in$ ...
h2. Date de ieşire
In fisierul de iesire $planeta.out$ veti afisa o permutare a numerelor de la $1$ la $N$, reprezentand cea de a $K$-a _parcurgere in pre-ordine_ din punct de vedere lexicografic.
În fişierul de ieşire $planeta.out$ ...
h2. Restricţii
* $1 ≤ N ≤ 30$
* $K$ va fi un numar intreg ce se va incadra pe $64$ de biti cu semn
* Se garanteaza ca exista cel putin $K$ parcurgeri in pre-ordine
* Pentru 30% din teste $1 ≤ N ≤ 10$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. planeta.in |_. planeta.out |
| 2 2
| 2 1 |
| 15 14023
| 1 2 3 4 5 15 8 7 6 14 9 12 10 11 13
|
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie
 
...
== include(page="template/taskfooter" task_id="planeta") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

3634