Úloha: Nejlevější maximální podstrom s vyhledávací vlastností

Nejprve zavedeme nezbytné pojmy.
Ve kořenovém stromu T je potomkem uzlu v každý uzel u různý od v, pro který platí, že v leží na cestě z kořene T do u. Uzel u je bezprostředním potomkem uzlu v pokud délka cesty z u do v je rovna 1. Pojmem strom budeme nadále v této úloze označovat vždy kořenový binární strom, tj. strom, v němž každý uzel má nejvýše jednoho bezprostředního levého a nejvýše jednoho pravého bezprostředního potomka.

Podstrom stromu T je množina uzlů A stromu T a množina H všech hran mezi uzly A s tou vlastností, že v T existuje uzel v, jehož množina všech potomků sjednocena s v je rovna množině A. Pravý, resp. levý podstrom uzlu u ve stromu T je takový podstrom S stromu T, že kořen S je levým, resp. pravým bezprostředním potomkem uzlu u.

Velikost podstromu je definována jako počet uzlů tohoto podstromu. V alespoň dvouprvkové možině podstromů je maximální každý podstrom, pro nějž platí, že jeho velikost je větší nebo rovna velikosti každého jiného podstromu v této množině. Strom v jednoprvkové množině stromů je vždy maximální.

Řekneme, že uzel u leží vlevo od uzlu v, pokud buď u leží levém podstromu v nebo v leží v pravém podstromu u nebo existuje uzel w, takový, že u leží v jeho levém podstromu a v leží v jeho pravém podstromu. Řekneme, že podstrom L leží vlevo od podstromu R, pokud kořen L leží vlevo od kořene R.

V této úloze předpokládáme, že každý uzel stromu obsahuje jeden nezáporný celočíselný klíč a že všechny klíče ve stromu jsou navzájem různé.

Označme levý podstrom uzlu v symbolem L(v) a pravý podstrom uzlu v symbolem R(v). Řekneme, že podstrom S stromu T má vyhledávací vlastnost, pokud pro každý uzel v podstromu S platí zároveň:
    (1) když je L(v) neprázdný, pak hodnota klíče uzlu v je větší než hodnota všech klíčů v L(v) a
    (2) když je R(v) neprázdný, pak hodnota klíče uzlu v je menší než hodnota všech klíčů v R(v).

Pro každé dva maximální podstromy s vyhledávací vlastností A, B ve stromu T platí, že buď leží A vlevo od B nebo B leží vlevo od A. Proto také (díky konečné velikosti T, tranzitivitě, antisymetrii a antireflrexivitě relace "leží vlevo od") v množině všech maximálních podstromů s vyhledávací vlastností existuje jediný podstrom L takový, který leží vlevo ode všech ostatních maximálních podstromů s vyhledávací vlastností. Tento podstrom L nazveme nejlevějším maximálním podstromem s vyhledávací vlastností v daném stromu T. Prvek jednoprvkové množiny maximálních podstromů s vyhledávací vlastností je vždy nejlevější.

Úlohou je v daném stromu nalézt nejlevější maximální podstrom s vyhledávací vlastností.

Řádkový zápis stromu definujeme rekurzivně:
1. Řádkový zápis prázdného stromu T je prázdný řetězec.
2. Řádkový zápis neprázdného stromu T má tvar (<LST><K><RST>),
kde <LST> je řádkový zápis levého podstromu kořene T, <K> je zápis hodnoty klíče v kořenu T, <RST> je řádkový zápis pravého podstromu kořene T.

Ukázka
Strom T je znázorněn na schématu, uzly nejlevějšího maximálního podstromu s vyhledávací vlastností jsou zvýrazněny symbolem #. Podstrom s kořenem s klíčem 10 je rovněž maximální vyhledávací v T.

                ___[20]___________________              
      _________[30]     _______________[13]____________ 
 ____[111]____         #40#_______             _____[10]
[110]     [112]             ___#50#___      __[5]__     
                           #45#    #55#    [3]   [7]

Řádkový zápis stromu T má tvar ((((110)111(112))30)20((40((45)50(55)))13(((3)5(7))10))).

Vstup

Strom na vstupu je vždy neprázdný a může být zadán dvěma způsoby. Při prvním způsobu vstup obsahuje jediný řádek s řádkovým zápisem stromu bez úvodních nebo koncových mezer.
Při druhém způsobu vstup obsahuje dva řádky. První řádek obsahuje seznam klíčů stromu vypsaných v pořadí inorder a druhý řádek obsahuje seznam klíčů stromu vypsaných v pořadí preorder. Každé dva sousední klíče v každém seznamu jsou odděleny jedinou mezerou, žádné další mezery vstup neobsahuje.
Hloubka stromu na vstupu je nejvýše 30.

Výstup

Na výstupu je jediný řádek s pěti celými čísly charakterizujícími nalezený podstrom. Čísla jsou oddělena jednou mezerou a řádek neobsahuje úvodní mezery. V zadaném stromu T označme V nejlevější maximální podstrom s vyhledávací vlastností. Čísla na výstupu pak jsou následující v uvedeném pořadí:
    1. Hodnota klíče v kořeni V,
    2. počet uzlů V,
    3. hloubka kořene V (hloubka kořene T je 0),
    4. výšku stromu V, to jest počet hran na cestě mezi kořenem V a nejhlouběji položeným listem V,
    5. levé pořadí kořene V, to jest počet uzlů stromu T které leží vlevo od kořene V.
Vstupní data jsou zapsána v souboru stdin (na konzolovém vstupu), výstup se zapíše do souboru stdout (na konzolový výstup).

Příklad 1

Na vstupu je strom z ukázky:

110 111 112 30 20 40 45 50 55 13 3 5 7 10 
20 30 111 110 112 13 40 50 45 55 10 5 3 7 

Výstup:

40 4 2 2 5

Příklad 2

Na vstupu je strom zadaný svým řádkovým zápisem:

(((1)5(((2)3)4))6((8)7(9)))

Výstup:

4 3 2 2 4

Strom je znázorněn následujícím schématem, hledaný podstrom je zvýrazněn znakem #.

    ___________[6]_____    
 __[5]________     __[7]__ 
[1]       __#4#   [8]   [9]
       __#3#               
      #2# 

Testovací data

Veřejná data k úloze jsou k dispozici. Veřejná data jsou uložena také v odevzdávacím systému a při každém odevzdání/spuštění úlohy dostává řešitel kompletní výstup na stdout a stderr ze svého programu pro každý soubor veřejných dat.

Veřejná data