Fişierul intrare/ieşire:livada.in, livada.outSursăOJI 2010, clasa a 9-a
AutorRadu BorigaAdăugată deGavrilaVladGavrila Vlad GavrilaVlad
Timp execuţie pe test0.15 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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:

  1. pe câte rânduri din livadă există un soi majoritar;
  2. care este cel mai mare număr de pomi de acelaşi soi plantaţi în poziţii consecutive pe un rând.

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.

Date de ieşire

Fişierul de ieşire livada.out va conţine două linii:

  1. 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;
  2. 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.

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.

Exemplu

livada.inlivada.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

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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content