Hash Table

Posloupnost N celých čísel A = { a1, a2, ..., aN} ukládáme postupně v tomto pořadí do rozptylovací tabulky velikosti L, která je na začátku prázdná. Celkový počet kolizí, které nastanou během vkládání všech prvků A do tabulky, označme PK(L).
Pro účely této ulohy považujeme za kolizi každou situaci, kdy máme vypočtenou možnou pozici vkládaného klíče a přitom je tato pozice v tabulce obsazena jiným klíčem. Během procesu vložení jednoho klíče tedy může nastat více kolizí, resp. kolize nastávají tak dlouho, dokud v tabulce není nalezena volná pozice pro vkládaný klíč.

Lze očekávat, že pro dvě různé délky L1 ≠ L2 bude platit PK(L1) ≠ PK(L2). Naší úlohou bude odhalit nejpříznivější a nejméně příznivou délku tabulky pro všechny přípustné hodnoty L z daného intervalu hodnot L1..L2.

Tabulka používá strategii double hashing. Adresa klíče k se vypočte ze vztahu
adresa(k ) = k mod L.
Při kolizi se generují další adresy, kam se zkouší klíč uložit. Další adresy klíče k se vypočtou ze vztahu
adresa(k ) = (k mod L + s *(1 + k mod H1)) mod L,       kde s = 1, 2, 3, ...
a kde H1 je daná celočíselná kladná konstanta.
Délka tabulky L je povinně prvočíselná.

Prvky posloupnosti A jsou dány předpisem
ak = (k*B) mod C,    (k = 1, 2, .. N),
kde B a C jsou daná kladná celá čísla.

Vstup

Na vstupu jsou dva řádky. Prní řádek obsahuje specifikaci posloupnosti A, což jsou tři celá čísla B, C, N oddělená mezerou. Platí B, C < 1500000. Druhý řádek obsahuje také tři celá čísla L1, L2, H1, také oddělená mezerou, která charakterizují tabulku. L1 představuje dolní mez pro všechny zkoumané přípustné hodnoty L délky tabulky, L2 představuje horní mez. Hodnota H1 je parametr druhé hashovací funkce specifikované výše. Platí 2 ≤ N ≤ L1 ≤ L2 < 110000, interval L1..L2 obsahuje alespoň jednu přípustnou hodnotu L.

Výstup

Výstup obsahuje dva řádky. První řádek obsahuje dvě čísla Lmin a Rmin oddělená mezerou. Lmin je délka tabulky, pro níž je hodnota PK(L) minimální pro všechna přípustná L z intervalu L1..L2. Pokud stejný minimální počet kolizí nastal při více různých hodnotách délky L, rovná se Lmin nejmenší z těchto hodnot.
Číslo Rmin představuje průměrný počet kolizí na jeden vložený prvek, tj. hodnotu PK(Lmin)/N. Lmin a Rmin jsou odděleny mezerou.

Druhý řádek výstupu je strukturován stejně jako první, hodnoty v něm jsou Lmax a Rmax a týkají se hodnoty L pro níž je PK(L) maximální pro všechna přípustná L z intervalu L1..L2. Pokud stejný minimální počet kolizí nastal při více různých hodnotách délky L, rovná se Lmax největší z těchto hodnot. Číslo Rmax představuje průměrný počet kolizí na jeden vložený prvek, tj. hodnotu PK(Lmax)/N. Lmax a Rmax jsou odděleny mezerou.

Rmin a Rmax mají povinně právě dvě číslice za desetinnou tečkou, před desetinnou tečkou je vždy alespoň jedna číslice.

Příklad 1

Vstup: 
13 19 9
10 14 5
Výstup: 
11 0.33
13 0.44

Příklad 2

Vstup: 
17 19 9
10 20 7
Výstup: 
11 0.00
19 0.00

Příklad 3

Vstup: 
997 1009 100
100 200 97
Výstup: 
151 0.00
103 1.84

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