Lista de probleme 5

Filtrare

Se dă un vector cu n elemente, numere naturale. Verificați dacă vectorul are un element majoritar. Numim element majoritar o valoare pentru care numărul de apariții în vector este mai mare decât n/2.

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

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.

#4588 pin

Piticul Doc și-a securizat pin-ul cardului bancar într-un mod cunoscut doar de el. Pin-ul este format din exact 4 cifre. Doc dispune de o mulțime de informații numerice dispuse pe R rânduri. Fiecare cifră din pin-ul cardului bancar este un element majoritar pe rândul său, adică numărul de apariții ale cifrei respective este mai mare decât n / 2, unde n reprezintă numărul total de cifre de pe rândul respectiv. Tu poți afla pin-ul lui Doc sau crezi că a greșit securizarea pin-ului? Cunoscând numărul R de rânduri și numerele de pe fiecare rând, scrieţi un program care să determine pin-ul lui Doc.

#4654 kmajo

Se dă un șir A cu N elemente, numere naturale nenule, și un număr natural K. O subsecvență a șirului este un șir format din unul sau mai multe elemente aflate pe poziții consecutive în șirul inițial. Spunem că o valoare x se numește element majoritar al unei secvențe de lungime m, dacă ea apare în aceasta de cel puțin \( \left[ \frac{m}{2} \right] + 1\) ori. Să se afișeze valorile care sunt elemente majoritare pentru cel puțin o subsecvență de lungime mai mare sau egală cu K a șirului A.

Un vârcolac bântuie ulițele satului Bosston, semănând panică printre săteni. Satul Bosston este compus din 2*N săteni, fiecare dintre aceștia fiind rudă cu exact un vârcolac. Vârcolacii sunt codificați cu numere naturale. Pentru a afla care este vârcolacul care le cauzează probleme, aceștia s-au dus la vraciul local. Acesta a spus că, dacă există un vârcolac V astfel încât oricum s-ar împărți cei 2*N săteni în două grupuri de N săteni, există cel puțin un sătean în primul grup și cel puțin un sătean în al doilea care să fie rude cu V, atunci vârcolacul V sigur este cel care bântuie satul. Dacă nu există un astfel de vârcolac, atunci sătenii nu își pot da seama cine le bântuie satul.

Cunoscând N și indicii vârcolacilor cu care se înrudesc fiecare dintre cei 2*N săteni, să se determine vârcolacul care bântuie satul, în cazul în care acesta există.