VII Olimpiada Informatyczna 1999/2000
|
Zadanie: KOD
|
Autor: Wojciech Guzicki
|
Zawody II stopnia, dzień drugi | 10 lutego 2000 |
Plik źródłowy: | KOD.??? (np. pas, c, cpp) |
Plik wykonywalny: | KOD.exe |
Plik wejściowy: | KOD.in |
Plik wyjściowy: | KOD.out |
Drzewo binarne może być puste, albo składać się 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:
Rozważmy wszystkie k-wierzchołkowe drzewa BST, w wierzchołkach których umieszczono początkowe k liter alfabetu angielskiego. Wyobraźmy sobie listę kodów tych drzew, wypisanych w kolejności alfabetycznej. (n,k)-kodem nazywamy n-ty kod na tej liście.
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 dcbaNapis badc jest (7,4)-kodem i odpowiada mu następujące drzewo BST:
Napisz program, który:
W pierwszym i jedynym wierszu pliku tekstowego KOD.IN zapisane są dokładnie dwie dodatnie liczby całkowite n i k, oddzielone pojedynczym znakiem odstępu, 1<=k<=19. Liczba n nie przekracza liczby kodów drzew BST o k wierzchołkach.
W pierwszym i jedynym wierszu pliku tekstowego KOD.OUT powinno znajdować się słowo złożone z małych liter alfabetu angielskiego będące (n,k)-kodem.
Dla pliku wejściowego KOD.IN
11 4
poprawną odpowiedzią jest plik wyjściowy KOD.OUT
dacb