5. Ááále, to sa spraví... vzorové riešenie

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

1

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

2

1 5 30
30 50 10 20 40

0

1 5 27
30 50 10 20 40

1

3 1 20
10
10
10

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)\).

A, B, M = [ int(_) for _ in input().split() ]
data = [ [ int(_) for _ in input().split() ] for a in range(A) ]

pocet_mensich = sum( x<M for row in data for x in row )
pocet_vacsich = sum( x>M for row in data for x in row )
max_moze      = (A*B - 1) // 2
zmenit        = 0
zmenitelny    = lambda x: False

if pocet_mensich > max_moze:
    zmenit = pocet_mensich - max_moze
    zmenitelny = lambda x: x < M

if pocet_vacsich > max_moze:
    zmenit = pocet_vacsich - max_moze
    zmenitelny = lambda x: x > M

# pocet_internov[x] bude pocet internov, ktori vedia spravit presne x zmien
pocet_internov = [ 0 for _ in range(B+1) ]
for row in data:
    pocet_internov[ sum( zmenitelny(x) for x in row ) ] += 1

vybrat = 0
for b in range(B,0,-1):
    while zmenit > 0 and pocet_internov[b] > 0:
        pocet_internov[b] -= 1
        zmenit -= b
        vybrat += 1

print(vybrat)