Kod

Limit pamięci: 32 MB

Drzewo binarne może byc puste, albo składać sie z wierzchołka, do którego przyczepione są dwa drzewa, tzw. lewe i prawe poddrzewo. W każdym wierzchołku zapisana jest jedna litera alfabetu angielskiego. Wierzchołek drzewa, który nie znajduje się w żadnym poddrzewie, nazywamy korzeniem. Mówimy, że drzewo jest binarnym drzewem poszukiwań (BST), jeżeli dla każdego wierzchołka spełniony jest warunek, mówiący, że wszystkie litery z lewego poddrzewa wierzchołka występują w alfabecie wcześniej, niż litera zapisana w wierzchołku, natomiast wszystkie litery z prawego poddrzewa - później. Kodem drzewa BST nazywamy:

  • ciąg pusty (0-elementowy), gdy drzewo jest puste,
  • ciąg liter zaczynający się od litery zapisanej w korzeniu drzewa, po którym następuje kod lewego poddrzewa, a następnie kod prawego poddrzewa.
Rozważmy wszystkie -wierzchołkowe drzewa BST, w wierzchołkach których umieszczono początkowe liter alfabetu angielskiego. Wyobraźmy sobie listę kodów tych drzew, wypisanych w kolejności alfabetycznej. (n,k)-kodem nazywamy -ty kod na tej liście.

Przykład

Istnieje dokładnie 14 kodów 4-wierzchołkowych binarnych drzew poszukiwań, konkretnie (w kolejności alfabetycznej):

abcd abdc acbd adbc adcb bacd badc cabd cbad dabc dacb dbac dcab dcba
Napis badc jest (7,4)-kodem i odpowiada mu następujące drzewo BST:

Zadanie

Napisz program, który:

  • ze standardowego wejścia wczyta liczby i ,
  • wyznaczy -kod,
  • wypisze go na standardowe wyjście.

Wejście

W pierwszym i jedynym wierszu standardowego wejścia zapisane są dokładnie dwie dodatnie liczby całkowite i , oddzielone pojedynczym znakiem odstępu, . Liczba nie przekracza liczby kodów drzew BST o wierzchołkach.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia powinno znajdować się słowo złożone z małych liter alfabetu angielskiego będące -kodem.

Przykład

Dla danych wejściowych:

11 4

poprawną odpowiedzią jest:

dacb

Autor zadania: Wojciech Guzicki.