Editing 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 <code>m</code> rânduri paralele, iar pe fiecare rând a plantat exact câte <code>n</code> 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 <code>1</code> şi <code>p</code>.

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 <code>k</code> format din <code>n</code> pomi fructiferi avem cel puţin <code>[n/2]+1</code> pomi de acelaşi soi <code>x</code>, atunci spunem că soiul <code>x</code> este soi majoritar pe rândul <code>k</code> (prin <code>[y]</code> se înţelege partea întreagă a numărului real <code>y</code>).

= Cerinţă =
Cunoscând numerele <code>m</code>, <code>n</code> şi <code>p</code>,  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.

= Date de intrare =
Fișierul de intrare <code>livada.in</code> conține pe prima linie trei numere naturale <code>m</code>, <code>n</code> şi <code>p</code> cu semnificaţia din enunţ, iar pe fiecare dintre următoarele <code>m</code> linii se găsesc câte <code>n</code> 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 <code>livada.out</code> 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 număr de pomi de același soi plantaţi în poziţii consecutive pe un rând.

= Restricții și precizări =

* <code>1 ≤ m ≤ 100</code>
* <code>1 ≤ n ≤ 700.000</code>
* <code>1 ≤ m*n ≤ 700.000</code>
* <code>1 ≤ p ≤ 998.560.000</code>
* Pe fiecare rând diferenţa dintre valoarea maximă şi cea minimă este cel mult <code>250.000</code>.
* 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: =
<code>livada.in</code>
 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
<code>livada.out</code>
 2
 3

= Explicație =
Plantaţia este formată din <code>m=4</code> rânduri, iar pe fiecare rând avem câte <code>n=7</code> pomi.

Pentru ca un soi sa fie majoritar pe un rând trebuie ca pe acel rând să existe cel puţin <code>[7/2]+1 = 4</code> pomi din soiul respectiv.

Există soiuri majoritare pe două rânduri: primul şi al treilea.

Pe rândul al treilea exista <code>3</code> poziții consecutive în care se află pomi din același soi (soiul <code>5</code>).

== Î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>