1080 - 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 număr de pomi de același soi plantaţi în poziţii consecutive pe un rând.

Restricții și precizări

• 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.in

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

livada.out

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 rândul al treilea exista 3 poziții consecutive în care se află pomi din același soi (soiul 5).

Încărcare soluție

Lipește codul aici

<syntaxhighlight lang="python" line="1"> def read_ints_from_file(file):

   return list(map(int, file.readline().split()))

def main():

   with open("livada.in", "r") as fin:
       m, n, p = read_ints_from_file(fin)
       max_length = 0
       rsm = 0
       for i in range(m):
           v = read_ints_from_file(fin)
           rmax = 0
           j = 0
           while j < n - 1:
               k = j + 1
               while k < n and v[k] == v[j]:
                   k += 1
               if k - j > rmax:
                   rmax = k - j
               j = k
           if rmax > max_length:
               max_length = rmax
           sm = v[0]
           cnt = 1
           for j in range(1, n):
               if cnt == 0:
                   sm = v[j]
                   cnt = 1
               elif v[j] == sm:
                   cnt += 1
               else:
                   cnt -= 1
           if cnt == 0:
               sm = 0
           else:
               cnt = sum(1 for x in v if x == sm)
               if cnt < n // 2 + 1:
                   sm = 0
           if sm != 0:
               rsm += 1
   with open("livada.out", "w") as fout:
       fout.write(f"{rsm}\n{max_length}")

if __name__ == "__main__":

   main()

</syntaxhighlight>