Mediány

Zadání

V této úloze budeme uvažovat neprázdné posloupnosti celých čísel, číslované počínaje indexem 1.

Uspořádáním posloupnosti A = (a₁, a₂, …, a_n) rozumíme posloupnost B = (b₁, b₂, …, b_n), jejíž prvky jsou uspořádány v neklesajím pořadí a přítom B je permutací prvků A.

Pro každou posloupnost A = (a₁, a₂, …, a_n), kde n je liché číslo, definujeme spodní celočíselný medián A jako číslo rovné prvku s indexem (n+1)/2 v uspořádání A.

Pro každou posloupnost A = (a₁, a₂, …, a_n), kde n je sudé číslo, definujeme spodní celočíselný medián A jako dolní celou část aritmetického průměru prvků s indexy n/2 a n/2+1 v uspořádání A.

Spodní celočíselný medián posloupnosti A označíme symbolem SCM(A).

Pro danou posloupnost A = (a₁, a₂, …, a_n), kde n > 1, definujeme levou částečnou mediánovou posloupnost C = (c₁, c₂, …, c_n−1) takto:

Pro 1 ≤ i ≤ n−1 je c_i = SCM(a₁, a₂, a₃, …, a_i+1).

Levou částečnou mediánovou posloupnost posloupnosti A označíme symbolem LCMP(A).

Pro danou posloupnost A = (a₁, a₂, …, a_n) a pro kladné celé číslo k (k < n) rekurzivně definujeme k-iterovanou levou částečnou mediánovou posloupnost, kterou označíme symbolem LCMP(A)^(k), takto:

Pro k = 1, je LCMP(A)^(k) = LCMP(A),
pro k > 1, je LCMP(A)^(k) = LCMP(LCMP(A)^(k−1)).

Posloupnost A definujeme pomocí pěti celých kladných čísel P, Q, R, M, N takto:

a₁ = P,
a_i = (Q×a_i−1 + R) mod M, pro 2 ≤ i ≤ N.

Úloha

Pro danou posloupnost A a pro dané číslo k máme určit první a poslední prvek posloupnosti LCMP(A)^(k).

Vstup

Na vstupu je jeden řádek obsahující šest kladných celých čísel P, Q, R, M, N, k v tomto pořadí oddělených navzájem mezerou. Význam čísel je popsán v textu úlohy.

Hodnoty P, Q, R, M, nepřekročí 10⁵, hodnota N nepřekročí 10⁶, hodnota k nepřekročí 10, P < M, k < N.

Výstup

Na výstupu je jeden textový řádek s dvěma celými čísly oddělenými mezerou. První číslo představuje první prvek posloupnosti LCMP(A)^(k) a druhé číslo představuje její poslední prvek.

Příklady

Příklad 1

Vstup

3 4 5 10 6 2

Výstup

4 5

A = (3, 7, 3, 7, 3, 7),

LCMP(A)⁽¹⁾ = (5, 3, 5, 3, 5),

LCMP(A)⁽²⁾ = (4, 5, 4, 5).

Příklad 2

Vstup

8 2 5 11  8 2

Výstup

8 5

A = (8, 10, 3, 0, 5, 4, 2, 9),

LCMP(A)⁽¹⁾ = (9, 8, 5, 5, 4, 4, 4),

LCMP(A)⁽²⁾ = (8, 8, 6, 5, 5, 5).

Příklad 3

Vstup

1401 14087 30211 98191 1000000 10

Výstup

22664 49407

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