Fişierul intrare/ieşire:	planeta.in, planeta.out	Sursă	Stelele Informaticii 2009, clasele 9-10
Autor	Andrei Grigorean	Adăugată de	Andrei Grigorean •wefgef
Timp execuţie pe test	0.1 sec	Limită de memorie	5120 kbytes
Scorul tău	N/A	Dificultate	N/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

Cum se trimit solutii?