Polish version    English version  
  O olimpiadzie -> Zadania -> VII OI 1999/2000


 Aktualności
 O olimpiadzie
O olimpiadzie
Zadania
I OI 1993/1994
II OI 1994/1995
III OI 1995/1996
IV OI 1996/1997
V OI 1997/1998
VI OI 1998/1999
VII OI 1999/2000
VIII OI 2000/2001
IX OI 2001/2002
X OI 2002/2003
XI OI 2003/2004
XII OI 2004/2005
XIII OI 2005/2006
XIV OI 2006/2007
XV OI 2007/2008
Archiwum zadań
Ankieta OI
 Komitety
 XVIII OI 2010/2011
 Historia OI
 Książeczki OI
 Reprezentacja
 Obozy Olimpiady
 Galeria zdjęć
 Ciekawe odsyłacze
 OIG LiveCD
 IV OIG 2009/2010
 Historia OIG
 SIO
 MAIN
VII Olimpiada Informatyczna 1999/2000

Zadanie: KOD
Autor: Wojciech Guzicki
Kod

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:

  • 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 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.

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:

  • z pliku tekstowego KOD.IN wczyta liczby n i k,
  • wyznaczy (n, k)-kod,
  • zapisze go do pliku tekstowego KOD.OUT.

Wejście

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.

Wyjście

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.

Przykład

Dla pliku wejściowego KOD.IN

11 4

poprawną odpowiedzią jest plik wyjściowy KOD.OUT

dacb



Wersja do druku