Enunțul problemei livada, de clasa a 9-a, dată în 2010 la OJI, se găsește pe PbInfo, .campion și InfoArena.

Rezumat livada

Se dă o livadă sub forma unei matrice cu m linii și n coloane. În fiecare celulă a matricei se află câte un pom, cu soiul identificat printr-un număr natural cuprins între 1 și p. Trebuie să aflăm pe câte linii ale matricei există un element majoritar, precum și cel mai mare număr de pomi de același soi, plantați pe poziții consecutive pe un rând. Într-un vector, un element se numește majoritar dacă acesta apare de mai mult de [n / 2] ori.

Soluție livada

Pentru prima cerință, trebuie să testăm pentru fiecare linie a matricei (liniile fiind considerate vectori) dacă aceasta are un element majoritar, folosind algoritmul clasic de complexitate $O(n)$. Se inițializează o variabilă cand (candidat) cu o valoare din afara intervalului [1, p], de exemplu 0, și o variabilă ap, ce semnifică numărul de apariții ale lui cand pe linia curentă. Parcurgem linia, iar dacă ap a ajuns la valoarea 0, schimbăm cand în v[i]. Altfel, dacă cand este egal cu elementul curent, incrementăm numărul său de apariții, iar dacă e diferit, îl decrementăm pe ap. La final, mai parcurgem o dată vectorul, pentru a număra aparițiile lui cand. Dacă numărul lor este într-adevăr ma mare decât n / 2, înseamnă că vectorul respectiv are un element majoritar.

A doua cerință este o simplă problemă cu secvențe. Folosim o variabilă lg, inițializată cu 0, ce reține lungimea secvenței curente. Dacă elementul curent este egal cu precedentul, incrementăm lg. Dacă nu, actualizăm lungimea maximă (dacă e cazul) și resetăm lg la 1. La primul pas, elementul precedent este 0 (pentru că am declarat vectorul global), ceea ce este OK, căci nu poate exista un soi codificat cu 0, așa că mereu v[0] != v[1]. Am ales să parcurg elementele până la poziția n + 1 (unde avem tot 0), ca să luăm în calcul și secvența care se termină pe poziția n.

Ca detalii de implementare: Am citit, pe rând, fiecare linie în vectorul v, pentru că n-are sens să rețin toată matricea. Apoi, am apelat funcția elMaj, ce verifică dacă v are element majoritar, și funcția secv, care parcurge secvențele de elemente egale din v. La final, am afișat cele două numere (nrMaj, lgMax). Se observă că p nu influențează cu nimic problema.

Sursă C++ livada

Dacă ai vreo nedumerire cu privire la problema livada, lasă un comentariu și te voi ajuta 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!