Koniec kola: 5. august 2019 23:59
17 days
Počet bodov:
Popis:  8b
Program:  12b

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

Odovzdávanie

Na odovzdávanie sa musíš prihlásiť

Otázky a diskusia

Po skončení kola budete mať príležitosť na diskutovanie o riešeniach v diskusii pod vzorovým riešením.