English
Zobacz więcej:
- dla uczniów szkół podstawowych: oij.edu.pl/start/
- dla uczniów szkół średnich: oi.edu.pl/l/jak_zaczac/
Zadanie Kod (kod)
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.
-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):
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.