Fișierul intrare/ieșire majoritate.in, majoritate.out Sursă ad-hoc
Autor autor necunoscut Adăugată de avatar francu Cristian Frâncu francu
Timp de execuție pe test 0.2 sec Limită de memorie 65536 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

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.in majoritate.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 3 categorii