Livada

livada

== include(page="template/taskheader" task_id="livada") ==

Norocosul Gigel tocmai a primit în dar de la bunicul său, Nelu, o imensă plantaţie de pomi fructiferi. Fost profesor de geometrie, Nelu a plantat în mod riguros pomii fructiferi pe $m$ rânduri paralele, iar pe fiecare rând a plantat exact câte $n$ pomi fructiferi. Însă, din motive mai mult sau mai puţin obiective, domnul Nelu nu a plantat pe fiecare rând toţi pomii de acelaşi soi, ci din mai multe soiuri diferite. Soiurile de pomi plantaţi în livadă sunt codificate cu numere naturale cuprinse între $1$ şi $p$.
Cuprins de febra rigurozităţii matematice şi de cea a statisticii, Gigel a definit noţiunea de soi majoritar astfel: dacă pe un rând $k$ format din $n$ pomi fructiferi avem cel puţin $[n/2]+1$ pomi de acelaşi soi $x$, atunci spunem că soiul $x$ este soi majoritar pe rândul $k$ (prin $[y]$ se înţelege partea întreagă a numărului real $y$).
 
h2. Cerinţă
 
Cunoscând numerele $m$, $n$ şi $p$, precum şi soiul fiecărui pom de pe fiecare rând al plantaţiei, ajutaţi-l pe Gigel să determine:
 
# pe câte rânduri din livadă există un soi majoritar;
# care este cel mai mare număr de pomi de acelaşi soi plantaţi în poziţii consecutive pe un rând.

Poveste şi cerinţă...

h2. Date de intrare

Fişierul de intrare $livada.in$ conţine pe prima linie trei numere naturale $m$, $n$ şi $p$ cu semnificaţia din enunţ, iar pe fiecare dintre următoarele $m$ linii se găsesc câte n numere, despărţite prin câte un spaţiu, reprezentând soiurile pomilor de pe rândul respectiv.

Fişierul de intrare $livada.in$ ...

h2. Date de ieşire

Fişierul de ieşire $livada.out$ va conţine două linii:
 
# pe prima linie se va scrie un număr natural reprezentând numărul de rânduri din livadă pe care există un soi majoritar;
# pe a doua linie se va scrie un număr natural reprezentând cel mai mare numar de pomi de acelasi soi plantaţi în poziţii consecutive pe un rând.

În fişierul de ieşire $livada.out$ ...

h2. Restricţii

* $1 ≤ m ≤ 100.$
* $1 ≤ n ≤ 700.000.$
* $1 ≤ m*n ≤ 700.000.$
* $1 ≤ p ≤ 998.560.000.$
* Pe fiecare rând diferenţa dintre valoarea maximă şi cea minimă este cel mult $250.000$.
* Dacă doar valoarea de pe prima linie este corectă, se acordă $40%$ din punctaj. Dacă doar valoarea de pe a doua linie este corectă, se acordă $60%$ din punctaj. Dacă ambele valori sunt corecte, se acordă $100%$ din punctajul testului respectiv.
 

* $... ≤ ... ≤ ...$

h2. Exemplu
table(example). |_. livada.in |_. livada.out |

| 4 7 9
2 1 2 3 8 2 2
4 7 2 4 9 7 4
5 5 2 5 5 5 7
2 3 2 3 2 3 1
|2
3

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

|
h3. Explicaţie

Plantaţia este formată din $m = 4$ rânduri, iar pe fiecare rând avem câte $n = 7$ pomi. Pentru ca un soi sa fie majoritar pe un rând trebuie ca pe acel rând să existe cel puţin $[7/2]+1 = 4$ pomi din soiul respectiv. Există soiuri majoritare pe două rânduri: primul şi al treilea. Pe randul al treilea exista $3$ pozitii consecutive in care se afla pomi din acelasi soi (soiul $5$).

...

== include(page="template/taskfooter" task_id="livada") ==

4628