Fişierul intrare/ieşire:planeta.in, planeta.outSursăStelele Informaticii 2009, clasele 9-10
AutorAndrei GrigoreanAdăugată dewefgefAndrei Grigorean wefgef
Timp execuţie pe test0.2 secLimită de memorie5120 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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:

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?

Date de intrare

Pe prima liniei a fisierului de intrare planeta.in contine doua numere intregi N si K, avand semnificatia din enunt.

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.

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

Exemplu

planeta.inplaneta.out
2 2
2 1
15 14023
1 2 3 4 5 15 8 7 6 14 9 12 10 11 13
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content