Zadanie

V okolí reaktoru vraj nejak stúpala radiácia, a tak každý intern vyfasoval jeden Geigerov-Müllerov počítač a poďho do terénu.

A ozaj, ony tie merania vyšli nejak divne. Ale to je určite len nejaká fluktuácia chalani, do reportu to tak nepíšte. Trošku to upravte, tak žeby dobre bolo, a ono to určite samo časom prejde.

Úloha

Je \(a\) internov, každý spravil presne \(b\) meraní. Čísla \(a\) a \(b\) sú obe nepárne.

Medián všetkých meraní je hodnota, ktorá by bola uprostred, keby sme ich všetky usporiadali podľa veľkosti. Do reportu by sme potrebovali napísať také merania, ktorých medián bude presne \(m\).

Každý intern môže klamať, a to tak, že prepíše nejaké svoje merania na ľubovolné hodnoty. Koľko najmenej internov musí v reporte klamať?

(Každý intern musí do reportu napísať nejakých \(b\) čísel. Ak intern klame, nemusí nutne zmeniť všetky svoje hodnoty, môže upraviť len ľubovoľnú ich podmnožinu.)

Formát vstupu

V prvom riadku vstupu sú čísla \(a\), \(b\) a \(m\). V každom z nasledujúcich \(a\) riadkov je \(b\) čísel: merania spravené jedným z internov.

Všetky výsledky meraní aj číslo \(m\) sú celé čísla z rozsahu od 0 po 99. (Keď intern klame, môže do reportu uviesť aj iné čísla, ak chce.)

Hodnoty \(a\) a \(b\) sú kladné celé čísla. V jednotlivých sadách platia nasledovné obmedzenia pre ich súčin:

Sada 1 2 3 4
\(\max a\times b\) 7 99 999 \(99\,999\)

Formát výstupu

Vypíšte jeden riadok a v ňom jedno číslo: minimálny počet internov, ktorí musia v reporte klamať, ak potrebujeme, aby medián všetkých \(a\times b\) meraní vyšiel presne \(m\).

Príklady

Input:

5 5 8
1 2 3 4 5
10 9 8 7 6
25 24 23 22 21
18 16 17 19 20
11 13 12 14 15

Output:

1

Momentálne je medián všetkých meraní rovný 13. Na to, aby sa zmenšil na 8, napríklad stačí, ak štvrtý intern namiesto 18,16,17,19,20 dá do reportu 3,1,3,5,7.

Input:

5 5 8
1 2 25 24 23
3 4 22 21 20
5 6 19 18 17
7 16 15 14 13
8 12 11 10 9

Output:

2

Tu namerali interni tých istých 25 hodnôt, ale pri tom, ako ich majú teraz rozdelené, nestačí, aby klamal len jeden z nich.

Input:

1 5 30
30 50 10 20 40

Output:

0

Input:

1 5 27
30 50 10 20 40

Output:

1

Input:

3 1 20
10
10
10

Output:

2

Začneme tým, že si vyriešime jednoduchšiu úlohu: odignorujeme zatiaľ, že máme nejakých internov, a budeme sa zaujímať len o to, koľko najmenej čísel treba zmeniť, aby medián vyšiel presne \(m\).

Predstavme si, že sme si všetky hodnoty usporiadali a pozreli sme sa do stredu poľa. Ak v strede poľa vidíme želanú hodnotu \(m\), netreba meniť nič.

Ak vidíme hodnotu menšiu ako \(m\), máme v poli priveľa malých čísel. Zistime si teda, pokiaľ v našom poli siahajú čísla menšie ako \(m\). Nech sú primalé čísla nielen v strede poľa, ale aj na nasledujúcich \(x-1\) políčkach. Čo to pre nás znamená? Aspoň \(x\) spomedzi čísel v pôvodnom poli nutne musíme zväčšiť na aspoň \(m\), inak budeme mať ešte stále priveľa malých čísel a v strede usporiadaného poľa bude naďalej primalá hodnota.

Na druhej strane však ľahko nahliadneme, že keď zmeníme ľubovoľných \(x\) primalých hodnôt na hodnotu presne \(m\), dostaneme platné riešenie. Totiž keď po tejto zmene preusporiadame prvky, prvky s novou hodnotou \(m\) obsadia presne \(x\) posledných políčok z úseku, v ktorom dovtedy boli primalé hodnoty – a teda aj v strede poľa už dostaneme hodnotu \(m\).

Situácia, keď sme v strede poľa uvideli priveľkú hodnotu, sa rieši symetricky.

Späť k pôvodnej úlohe

Bez ujmy na všeobecnosti predpokladajme, že súčasný medián je primalý, potrebujeme teda niektoré prvky zväčšiť. A vyššie popísaným spôsobom vieme nájsť \(x\) také, že určite treba spraviť aspoň \(x\) zmien.

Pre každého interna si teraz zistíme, koľko má medzi svojími meraniami čísel menších ako \(m\). Nanajvýš toľko ich samozrejme tento konkrétny intern vie zväčšiť na \(m\). My hľadáme takú sadu internov, aby ich bolo čo najmenej a aby dokopy vedeli zväčšiť aspoň tých potrebných \(x\) hodnôt. Je zjavné, že toto vieme spraviť pažravo: usporiadame si internov podľa toho, koľko hodnôt vedia zväčšiť na \(m\), a budeme ich postupne brať (začínajúc tým, ktorý vie zmien spraviť najviac) až kým nebudú dokopy vedieť spraviť dostatočný počet zmien.

Zjavne platí, že keď nami vybraná skupina internov spraví ľubovoľných \(x\) zmien (hodnoty menšej ako \(m\) na hodnotu \(m\)), dostaneme platné riešenie. A tiež platí, že žiadna menšia skupina internov takto veľký počet zmien nevie spraviť, nájdené riešenie je teda optimálne.

Implementácia

K implementácii už len podotknem, že usporadúvať samotné čísla vôbec netreba – totiž si stačí v lineárnom čase spočítať, koľko je primalých a koľko je priveľkých. Pri usporadúvaní internov podľa počtu dobrých zmien, ktoré vedia spraviť, som použil CountSort, celkovo má teda nižšie uvedená implementácia časovú zložitosť lineárnu od veľkosti vstupu: \(O(ab)\).

Zdrojové kódy budú zverejnené až po 19.8. 23:59:59. Dovtedy sa môžete pokúsiť úlohu naprogramovať sami
(a získať tým nejaké body navyše).

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.