[naglowek]

wersja PS     wersja PS.ZIP
Wstęp
Sprawozdanie z przebiegu VII OI
Regulamin
Zasady organizacji zawodów
Informacja o IOI'99
Etap I
Etap II
 
Podpisy
Automorfizmy
Trójramienny dźwig
Kod
Labirynt studni
Etap III
IOI
Literatura

Spis treści
O wersji online

Niebieskie książeczki
 
Olimpiada Informatyczna
Kącik zadań
Archiwum zadań
CEOI'97
 
   Wojciech Guzicki (treść, opracowanie)    Marcin Mucha (program wzorcowy)

Kod

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 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:

 epsffilekod.1

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 le k le 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

Rozwiązanie

Zastanówmy się najpierw, ile jest drzew binarnych o zadanej liczbie wierzchołków. Oznaczmy przez Ck liczbę drzew mających k wierzchołków. Oczywiście C_0=1: tylko drzewo puste ma zero wierzchołków. Również jest tylko jedno drzewo mające jeden wierzchołek, zatem C_1=1. Niech teraz k będzie liczbą naturalną większą od jedności. Drzewo mające k wierzchołków składa się z korzenia, do którego przyczepione są dwa poddrzewa mające łącznie k-1 wierzchołków. Mamy więc k możliwości:

  • Przypadek 0. Lewe poddrzewo ma 0 wierzchołków, prawe ma k-1 wierzchołków (takich drzew jest oczywiście C_0cdot C_k-1).
  • Przypadek 1. Lewe poddrzewo ma 1 wierzchołek, prawe ma ich k-2 (takich drzew jest C_1cdot C_k-2);

   ...
  • Przypadek k-1. Lewe poddrzewo ma k-1 wierzchołków, prawe ma 0 wierzchołków (takich drzew jest C_k-1cdot C_0).
Stąd otrzymujemy następujący wzór rekurencyjny na liczbę drzew:

 C_k=C_0cdot C_k-1+C_1cdot C...

Liczby Ck nazywamy liczbami Catalana. Występują one w wielu innych zadaniach kombinatorycznych. Na przykład:

  • Liczba funkcji niemalejących

     f : 1,2,ldots,n to 1,2,ldo...

    tzn. takich, że jeśli kle l, to f(k)le f(l) dla dowolnych k,l in 1,2,ldots,n i spełniających warunek f(k)le k, dla każdego kin1,2,ldots,n, jest równa Cn.
  • Liczba różnych triangulacji (czyli sposobów podziału przekątnymi na trójkąty) wielokąta wypukłego mającego n boków jest równa C_n-2.
  • Przypuśćmy, że mamy dane działanie dwuargumentowe circ i rozważamy wyrażenie postaci x_1circ x_2circ ldotscirc x_n. W tym wyrażeniu możemy rozstawić nawiasy (tak, by zawsze wykonywać działanie na dwóch argumentach) na wiele sposobów. Na przykład, dla n=4 mamy następujące sposoby:

    displaylines (x_1circ x_2)cir...

    Liczba różnych sposobów rozstawienia nawiasów jest równa C_n-1. Inaczej mówiąc, jeśli działanie circ jest niełączne (przykładem takiego działania jest dzielenie liczb rzeczywistych dodatnich), to wykonując to działanie na wszystkie możliwe sposoby, z zachowaniem kolejności x_1,x_2,...,x_n, możemy otrzymać co najwyżej C_n-1 różnych wyników.
  • Liczby Catalana występują również jako rozwiązania następującego zadania: w kolejce do kina stoi 2n osób, n z nich ma tylko 5 złotych, każda z pozostałych ma tylko banknot dziesięciozłotowy. Bilet kosztuje 5 złotych. W kasie nie ma pieniędzy, więc może się okazać, że w którymś momencie kasjerka nie będzie mogła wydać reszty kolejnej osobie (na przykład, jeśli pierwsza osoba ma 5 złotych, a dwie następne po 10 złotych, to trzecia osoba nie otrzyma reszty i kolejka się zatrzyma). Okazuje się, że liczba sposobów ustawienia osób w kolejce tak, by wszyscy mogli kupić bilety, jest równa Cn.
Czytelnikowi zainteresowanemu kombinatoryką polecamy książki W. Lipski, W. Marek - Analiza kombinatoryczna i V. Bryant - Aspekty kombinatoryki, z których można dowiedzieć się więcej o liczbach Catalana.

Podany wyżej wzór rekurencyjny pozwala obliczyć kolejne liczby Catalana. Początkowe liczby Catalana są równe odpowiednio:

 eqalign C_0 &= 1, cr C_1 &= ...

Znany jest też wzór ogólny na k-tą liczbę Catalana. Mianowicie

 C_k = 1 over k+1 cdot 2k c...

W programie wzorcowym liczby Catalana są obliczane za pomocą wzoru rekurencyjnego.

Teraz opiszemy algorytm znajdowania (n,k)-kodu drzewa binarnego. Najpierw wyjaśnimy istotę działania tego algorytmu na przykładzie. Przyjmijmy k=10 i n=8751. Wiemy już, że istnieje 16796 drzew binarnych mających 10 wierzchołków. Ta liczba jest sumą następujących 10 liczb:


  1. liczby C_0 cdot C_9, równej 4862; jest to liczba tych drzew, w których lewe poddrzewo ma 0 wierzchołków, a prawe 9 wierzchołków; są to dokładnie te drzewa binarne, które mają w korzeniu umieszczoną literę a;


  2. liczby C_1 cdot C_8, równej 1430; jest to liczba tych drzew, w których lewe poddrzewo ma 1 wierzchołek, a prawe 8 wierzchołków; są to drzewa, które mają w korzeniu umieszczoną literę b;


  3. liczby C_2 cdot C_7, równej 858; jest to liczba tych drzew, w których lewe poddrzewo ma 2 wierzchołki, a prawe 7 wierzchołków; są to drzewa, które mają w korzeniu umieszczoną literę c;


   ...


  10. liczby C_9 cdot C_0, równej 4862; jest to liczba tych drzew, w których lewe poddrzewo ma 9 wierzchołki, a prawe 0 wierzchołków; są to drzewa, które mają w korzeniu umieszczoną literę j.

Kody wszystkich drzew z grupy pierwszej poprzedzają oczywiście w porządku alfabetycznym kody drzew z grupy drugiej, te z kolei poprzedzają kody drzew w grupy trzeciej itd. Zauważmy teraz, że łączna liczba kodów zaczynających się od liter a, b, c, d, e jest równa 8398 (czyli mniej niż 8751), a jeśli dopuścimy jeszcze literę f, to liczba kodów wyniesie 8986 (a więc więcej niż 8751). Stąd wynika, że pierwszą literą kodu jest f. Po niej nastąpią litery od a do e (w nieznanej jeszcze kolejności) i na końcu litery od g do j (również w nieznanej kolejności). W ten sposób ustaliliśmy pierwszą literę kodu drzewa. Następnie będziemy chcieli ustalić kody obu poddrzew. W tym celu obliczymy kolejne numery tych kodów i rekurencyjnie znajdziemy same kody.

Każdemu z C5 kodów złożonych z liter od a do e na początku odpowiada C4 kodów złożonych z liter od g do j na końcu. Mamy znaleźć 353-ci z kolei kod rozpoczynający się literą f (gdyż 8751-8398=353). Każdemu kodowi lewego poddrzewa odpowiada 14 kodów prawych poddrzew. Ale 352=25cdot14+2. Stąd wynika, że odcinek początkowy naszego kodu (po literze f) ma być dwudziestym szóstym z kolei kodem składającym się z liter od a do e, a odcinek końcowy ma być trzecim z kolei kodem składającym się z liter od g do j. Jest tak dlatego, że pierwszym dwudziestu pięciu kodom lewych poddrzew odpowiada tylko 25cdot 14 czyli 350 kodów całych drzew. Nasz kod ma więc być trzecim kodem z następnej, tzn. dwudziestej szóstej grupy. Powstaje pytanie, dlaczego dzielimy 352, a nie 353. Mianowicie mamy proste wzory ogólne na numer grupy (czyli numer kodu lewego poddrzewa) i numer w tej grupie (czyli numer kodu prawego poddrzewa):


   przypuśćmy, że nasz kod ma być m-tym kodem zaczynającym się od pewnej znanej już litery c (w naszym przypadku c=tt f); znamy więc wielkości obu poddrzew: niech lewe składa się z l wierzchołków, a prawe z p wierzchołków. Wtedy lewe poddrzewo ma numer (m-1) bf div C_p +1, a prawe (m-1) bf mod C_p +1.

Kontynuując obliczenia w naszym przykładzie zauważymy, że odcinek początkowy kodu zaczyna się literą d, po której następuje trzeci kod składający się z liter a, b, c i jedyny kod składający się z litery e. Odcinek końcowy zaczyna się literą g, po której następuje trzeci kod składający się z liter h, i, j. Ostatecznie otrzymamy kod fdbacegihj.

Teraz już nietrudno napisać odpowiedni algorytm rekurencyjny. Główna funkcja wyznaczająca (n,k)-kod ma w nim postać następującą. Argumentami funkcji są: litera cp, od której zaczynają się litery umieszczone w wierzchołkach drzewa (będzie to potrzebne w przypadku prawego poddrzewa, w którym występują litery nie od początku alfabetu), numer n drzewa i liczba wierzchołków k. W tablicy Catalan umieszczone są oczywiście liczby Catalana, obliczone wcześniej za pomocą wzoru rekurencyjnego. Na początku funkcja zwraca wartości w przypadkach najprostszych: kod pusty dla drzewa pustego i kod jednoliterowy cp dla drzewa składającego się z jednego wierzchołka. Dla drzew większych obliczamy w pętli sumę iloczynów liczb Catalana dotąd, aż przekroczy ona n. Zauważmy, że wartości zmiennych l i p są wtedy równe dokładnie liczbom wierzchołków w lewym i prawym poddrzewie. Korzeń otrzymujemy znajdując literę stojącą w alfabecie o l miejsc dalej od cp. Potem zgodnie z powyższymi wzorami znajdujemy numery lewego i prawego poddrzewa i dwukrotnie wywołujemy procedurę rekurencyjnie. Otrzymane kody drzew łączymy wreszcie ze znalezionym wcześniej korzeniem. Oto treść tej procedury:

1function Kod (cp : char; n : longint; k : integer) : String;
2      { cp : litera początkowa kodu drzewa;
3          n : numer kodu drzewa wśród drzew mających wierzchołki
4                    oznaczone literami począwszy od cp zakładamy, że liczba
5                    n nie przekracza liczby Catalana C[k];
6          k : liczba wierzchołków drzewa}
7var
8      l,p : integer; {liczba wierzchołków w lewym i prawym poddrzewie}
9      Suma : longint; {suma iloczynów liczb Catalana}
10      SumaPoprzednia : longint;
11      m : longint;
12      n1,n2 : longint; {numery lewego i prawego poddrzewa}
13      znak : char;
14begin
15      if (k=0) then
16            Kod:=`'
17      end if (k=1) then
18            Kod:=cp
19      end begin
20            Suma:=0;
21            l:=-1;
22            p:=k;
23            repeat
24                  l:=l+1;
25                  p:=p-1;
26                  SumaPoprzednia:=Suma;
27                  Suma:=Suma+Catalan[l]*Catalan[p];
28            until (Sumagen);
29            znak:=chr(ord(cp)+l);
30            m:=n-SumaPoprzednia;
31            n1:=((m-1) div Catalan[p])+1;
32            n2:=((m-1) mod Catalan[p])+1;
33            Kod:=znak+Kod(cp,n1,l)+Kod(succ(znak),n2,p)
34      end
35end;

Ten najprostszy program zamieszczony jest w pliku o nazwie kod0.pas. Nie jest on jednak optymalny. Można zauważyć, że pewne obliczenia są wykonywane wielokrotnie, na przykład sumowanie iloczynów liczb Catalana. Te iloczyny i ich sumy można obliczyć wcześniej i umieścić w tablicy. Tak napisany program znajduje się w pliku kod.pas.

Ograniczenie k=19 wynika z wielkości liczb Catalana. Liczba C_19=1767263190 mieści się jeszcze w zakresie liczb typu longint.

Testy

Do sprawdzania rozwiązań zawodników użyto 17 testów:

  • KOD0.IN - test z treści zadania,
  • KOD1.IN - n=3, k=3,
  • KOD2.IN - n=42, k=5,
  • KOD3.IN - n=1, k=6,
  • KOD4.IN - n=2000, k=9,
  • KOD5.IN - n=50000, k=11,
  • KOD6.IN - n=200000, k=13,
  • KOD7.IN - n=1000000, k=15,
  • KOD8.IN - n=20000000, k=17,
  • KOD9.IN - n=100000000, k=18,
  • KOD10.IN - n=400000000, k=19,
  • KOD11.IN - n=800000000, k=19,
  • KOD12.IN - n=100, k=19,
  • KOD13.IN - n=1767263190, k=19,
  • KOD14.IN - n=1111111111, k=19,
  • KOD15.IN - n=1234567890, k=19,
  • KOD16.IN - n=608197699, k=19.