Lista de probleme 6
Filtrare
Majoritar
#497
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.
Livada
#1080
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:
- 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.
OJI 2010, Clasa a IX-a
Candale Silviu (silviu)
Radu Boriga
concurs
Clasa 9
Tablouri unidimensionale (vectori)
Probleme diverse
Element majoritar
pin
#4588
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.
OMI Iasi 2024
Pracsiu Dan (dnprx)
Lucian Neagu
concurs
Clasa 9
Tablouri unidimensionale (vectori)
Parcurgerea vectorilor
Element majoritar
kmajo
#4654
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.
ONI 2024, clasa a 8-a
Pracsiu Dan (dnprx)
Bogdan Ioan Popa
concurs
Clasa 9
Tablouri unidimensionale (vectori)
Probleme cu secvențe
Two Pointers
Element majoritar
joc15
#4789
Jocul preferat al lui Aurel are o hartă împărțită în N sectoare, numerotate, în ordine, de la 1 la N. Fiecare sector i (1 ≤ i ≤ N) are asociate două numere naturale reprezentând un decor, decori și un scor, scori. Două decoruri de același tip sunt codificate prin același număr natural.
1) Determinați numărul de moduri în care Aurel poate începe jocul, astfel încât prima secvență pe care o “vede” pe hartă să NU fie riscantă. Două moduri de a începe jocul sunt considerate diferite dacă încep pe sectoare diferite sau dacă au vizibilitatea diferită.
2) Determinați scorul obținut dacă Aurel pornește din sectorul 1 cu vizibilitatea 0.
OJI 2025, clasa a 8-a
Pracsiu Dan (dnprx)
Dumitru Ilie
concurs
Clasa 9
Tablouri unidimensionale (vectori)
Probleme cu secvențe
Element majoritar
Avarcolaci
#1115
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ă.
ONI 2014, Clasele XI-XII
Candale Silviu (silviu)
Andrei Parvu
concurs
Clasa 11
Probleme diverse
Probleme diverse
Element majoritar