A2 - Kĺzavý medián

Časový limit: 5s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 1

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Úloha

V médiách sa často spomína týždenný kĺzavý medián ako jedno z hlavných kritérií hygienických opatrení proti šíreniu ochorenia COVID-19. Tento termín bol už aj zhudobnený. Viete ako sa počíta?

Napíšte program, ktorý pre zadané údaje vypočíta všetky kĺzavé mediány pre vybranú veľkosť časového okna (najčastejšie sa používa týždeň, ale môže to byť ľubovoľný počet dní). Medián je stredná hodnota, teda hodnota v strede po usporiadaní údajov. V matematike sa často v prípade párneho počtu hodnôt za medián považuje priemer prostredných dvoch hodnôt, ale vzhľadom na údaj o počte osôb (štatistikom by sa páčil medián 2521.5, ale pre interpretáciu na verejnosti je výhodnejšie pracovať s celými číslami), v našom prípade budeme teda za medián považovať menšiu hodnotu z prostredných dvoch.

Vstup

Prvý riadok obsahuje počet testovacích sád S. Každá testovacia sada začína riadkom obsahujúcim dve celé čísla, udávajúce počet údajov N a veľkosť okna 5 ≤ K ≤ N (počet údajov pre výpočet mediánu). Nasleduje v nej N riadkov obsahujúcich hodnoty H_i.

Výstup

Pre každú testovaciu sadu vypíšte príslušný počet (N-K+1) kĺzavých mediánov, každý zvlášť na samostatnom riadku.

A1

7 ≤ N ≤ 1.000
0 ≤ H_i ≤ 10.000

A2

7 ≤ N ≤ 1.000.000
0 ≤ H_i ≤ 1.000.000

Príklad

Vstup:

Výstup:

Údaje prvej testovacej sady reprezentujú 7-dňový kĺzavý medián počtu pozitívne testovaných osôb na Slovensku k 24.-26.1.2021

19 Domáce 1