Raul: Pagină nouă: 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...

2024-02-13T14:48:17Z

Pagină nouă: 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...

New page

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>

1080 - Livada - Revision history