Laser

Stínítko je během pokusu osvětleno vícekráte zábleskem laseru. Stínítko má tvar obdélníku o šířce 1 metru a velmi malé výšce, pro naši úlohu zanedbatelné. Delší strana stínítka je orientována vodorovně. Horizontální polohu místa na stínítku, na které dopadne světlo při jednom zablesknutí laseru je možno určit s přesností 10−P metrů. Např. pro P=3 je možno detekovat 103+1 poloh záblesku na stínítku včetně jeho pravého a levého okraje. Jeden záblesk osvítí stínítko v úseku < X− D⋅10−P, X+D⋅10−P>, kde X je změřená poloha dopadu záblesku na stínítko a D známý konstantní celočíselný parametr. Záblesk osvítí stínítko v celé jeho výšce.

Během pokusu je provedeno právě L záblesků. Výsledkem pokusu je posloupnost X1, X2, ..., XL změřených poloh dopadu záblesků na stínítko.

Díky značně chaotickému výběru směru jednotlivých záblesku je posloupnost změřených poloh generována předpisem:
Y1 = Z
Yi+1 = [4 × Yi × (1 − ( Yi /10P)]    pro Yi ≠ 0,
Yi+1 = 1    pro Yi = 0,
Xi = Yi× 10−P.
Závorky [] představují dolní celou část argumentu, celočíselná konstanta Z je dána na začátku pokusu.

Pokus začíná s dosud nepoužitým stínítkem. Když na některé místo stínítka dopadne K nebo více záblesků, stínítko v tomto místě ztmavne. Po ukončení pokusu se tak na stínítku střídají tmavší a světlejší úseky. Úlohou je určit délku nejkratšího a nejdelšího tmavého úseku po ukončení pokusu a celkovou délku tmavých úseků.

Vstup

Na vstupu je jeden řádek s pěti celými čísly P, D, L, K, Z popsanými výše. Čísla jsou navzájem oddělena mezerou. Číslo P může nabývat hodnot 1, 2, ..., 11, číslo D může nabývat hodnot 1, 2, ..., 108, číslo L může nabývat hodnot 1, 2, ..., 105, číslo K může nabývat hodnot 1, 2, ..., L+1, číslo Z může nabývat hodnot 1, 2, ..., 10P.

Výstup

Na výstupu je řádek se třemi celými čísly A, B, C v tomto pořadí a oddělenými mezerou, přičemž postupně A×10−P, B×10−P, C×10−P představují délky nejkratšího a nejdelšího tmavého úseku po skončení pokusu a celkovou délku tmavých úseků.

Poznámka

Data úlohy byla dodatečně aktualizována (30.03, 01:10), ujistěte se, že také používáte jejich aktuální verzi.

Příklad 1

Vstup: 
1 2 3 1 4
Výstup: 
3 5 8

Příklad 2

Vstup: 
1 1 3 1 5
Výstup: 
1 2 4

Příklad 3

Vstup: 
2 20 4 2 13
Výstup: 
8 23 31

Příklad 4

Vstup: 
11 100000 100000 2 402333
Výstup: 
3 11108150 2167468774

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