Fişierul intrare/ieşire:majoritate.in, majoritate.outSursăad-hoc
AutorAutor NecunoscutAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.2 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Majoritate (clasa a 9-a)

Majoritatea unui şir de numere naturale este numărul maxim de apariţii ale unui număr din şir. De exemplu şirul 2 4 2 3 4 2 3 4 are majoritate 3, deoarece numărul maxim de apariţii ale unui număr este 3 (numerele 2 şi 4 apar de trei ori).

Dorim să găsim subşirul cu majoritate maximală de lungime minimă. În exemplul anterior subşirul cu majoritate maximală de lungime minimă este 2 4 2 3 4 2. Există un al doilea subşir de majoritate maximală, dar nu de lungime minimă: 4 2 3 4 2 3 4.

Cerinţă

Dându-se un şir de numere naturale să se afişeze indicii de început şi de sfârşit ai subşirului cu majoritate maximală de lungime minimă. Dacă există mai multe astfel de subşiruri se va afişa cel al cărui indice de început este minim.

Date de intrare

Fişierul de intrare majoritate.in conţine pe prima linie numărul de elemente ale şirului, n. Pe a doua linie conţine cele n numere ale şirului.

Date de ieşire

În fişierul de ieşire majoritate.out veţi scrie două numere, s şi d, despărţite prin spaţiu, reprezentând indicii de început şi sfârşit ai subşirului găsit.

Restricţii

  • 1 ≤ n ≤ 100 000
  • 1 ≤ elementele şirului ≤ 1 000 000
  • pentru 25% din teste n ≤ 2300
  • pentru 50% din teste n ≤ 15000

Exemplu

majoritate.inmajoritate.outExplicaţie
8
2 4 2 3 4 2 3 4
1 6
Subşirul minim de majoritate maximală începe la indicele 1 şi se termină la indicele 6
el fiind 2 4 2 3 4 2. Majoritatea maximală este 3 (numărul de apariţii ale lui 2).
5
1 1 2 2 1
1 5
Subşirul minim de majoritate maximală începe la indicele 1 şi se termină la indicele 5
el fiind întregul şir.
5
1 2 2 3 1
2 3
Subşirul minim de majoritate maximală începe la indicele 2 şi se termină la indicele 3
el fiind 2 2.
6
1 2 2 1 1 2
1 5
Subşirul minim de majoritate maximală începe la indicele 1 şi se termină la indicele 5
el fiind 1 2 2 1 1.
Trebuie sa te autentifici pentru a trimite solutii. Click aici