Potenciál uzlu binárního stromu

Nechť H je neprázdná konečná množina čísel. Levý medián množiny H definujeme jako takové číslo x, které je rovné některému prvku H a pro které platí:
Je-li |H| liché, pak v H existuje právě (|H|-1)/2 prvků větších než x.
Je-li |H| sudé, pak v H existuje právě |H|/2 prvků větších než x.

Nechť S je neprázdný soubor celých čísel, v němž se libovolné hodnoty mohou libovolněkrát opakovat, a nechť H je množina všech hodnot (bez opakování), které se vyskytují v S. Definujeme redukovaný levý medián souboru S jako číslo, které je rovno levému mediánu množiny H .
Příklad. Redukovaný levý medián souboru S = (5, 1, 4, 4, 2, 4) je 2.

Nechť T je neprázdný binární strom, jehož každý uzel obsahuje právě jeden celočíselný klíč. Klíč uzlu x označíme symbolem K(x).
Nechť x a y jsou uzly stromu T. Řekneme, že uzel y je volným potomkem uzlu x, pokud uzel x leží na cestě z uzlu y do kořene T. Připomeňme, že uzel leží na cestě, je-li některým jejím vnitřním nebo krajním uzlem.
Definujeme podstrom v uzlu x jako jako strom, jehož kořenem je uzel x a který obsahuje všechny volné potomky uzlu x. Podstrom v uzlu x označíme symbolem T(x). Označme symbolem LT(x) množinu všech listů T(x) a symbolem RLM(x) redukovaný levý medián souboru všech klíčů množiny LT(x).
Potenciálem uzlu x nazveme součin K(x) × RLM(x).

Úloha
V daném binárním stromu máme najít minimální a maximální hodnotu potenciálu všech jeho vnitřních uzlů.

Obr. 1. Příklad. Potenciál uzlu x ve stromu na obrázku je roven 14.


Pro danou pětici celých kladných čísel (A, C, M, Z, D) definujeme binární strom T asociovaný s pěticí (A, C, M, Z, D) takto:
0. Pro dané celé číslo n označme F(n) hodnotu (A×n + C) mod M.
1. Každý uzel T obsahuje jeden celočíselný klíč K(x).
2. Hloubka T je nejvýše D.
3. Uzel x má levého potomka, pokud (K(x) mod 4) ∈ {1, 3}.
4. Uzel x má pravého potomka, pokud (K(x) mod 4) ∈ {2, 3}.
5. Když je uzel y levým potomkem uzlu x, pak K(y) = F(K(x)+1).
6. Když je uzel y pravým potomkem uzlu x, pak K(y) = F(K(x)+2).
7. Pro kořenem k stromu T platí K(k) = Z.

Vstup

Na vstupu je jeden textový řádek, který obsahuje kladná čísla A, C, M, Z, D v tomto pořadí oddělená mezerou.
Hodnoty A, C, M, Z nepřekročí 106, hodnota D nepřekročí 100. Strom asociovaný s pěticí (A, C, M, Z, D) obsahuje alespoň 2 uzly a nejvýše 1.5×105 uzlů.

Výstup

Na výstupu je jeden textový řádek obsahující dvě celá čísla oddělená mezerou. První číslo představuje minimální hodnotu potenciálu všech vnitřních uzlů ve stromu asociovaném s pěticí (A, C, M, Z, D), druhé číslo představuje maximální hodnotu potenciálu všech vnitřních uzlů ve stromu asociovaném s pěticí (A, C, M, Z, D).

Příklad 1

Vstup:
4 3 20 5 4
Výstup:
9 285

Obr. 2. Ilustrace k příkladu 1. Strom asociovaný s pěticí (4, 3, 20, 5, 4).

Příklad 2

Vstup:
95457 29573 223451 41931 100
Výstup:
166254288 38669346056
Pro kontrolu uvádíme, že strom asociovaný s pěticí (95457, 29573, 223451, 41931, 100) obsahuje 113 uzlů.

Příklad 3

Vstup:
28664 25355 132406 16141 26
Výstup:
9763 17306640741
Pro kontrolu uvádíme, že strom asociovaný s pěticí (28664, 25355, 132406, 16141, 26) obsahuje 129763 uzly.

Veřejná 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