Fişierul intrare/ieşire: | majoritar.in, majoritar.out | Sursă | Cerc informatică Vianu |
Autor | Din Folclor | Adăugată de | |
Timp execuţie pe test | 2 sec | Limită de memorie | 32768 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Elementul Majoritar (clasa a 6-a)
Dat un şir cu N elemente să se spună dacă conţine un element majoritar. Un element majoritar este un element care apare de cel puţin N / 2 + 1 ori. Încercaţi să daţi o soluţie mai bună decât sortarea.
Date de intrare
Fişierul de intrare majoritar.in conţine pe prima linie numărul N, iar pe urmatoarele N linii, câte un număr natural.
Date de ieşire
În fişierul de ieşire majoritar.out se găsesc două numere naturale separate printr-un spaţiu. Primul număr semnifică valoarea elementului majoritar, iar cel de-al doilea, numărul de apariţii ale acestuia. În cazul în care nu există un astfel de element, se va afişa -1.
Restricţii
- 1 ≤ N ≤ 3.000.000
- 1 ≤ v[i] ≤ 1.000.000.000, unde v[i] este element al şirului.
Exemplu
majoritar.in | majoritar.out |
---|---|
11 3 4 4 3 4 4 3 4 2 4 3 | 4 6 |