Fișierul intrare/ieșire | majoritate.in, majoritate.out | Sursă | ad-hoc |
---|---|---|---|
Autor | autor necunoscut | Adăugată de | Cristian Frâncu • francu |
Timp de execuție pe test | 0.2 sec | Limită de memorie | 65536 KB |
Scorul tău | N/A | Dificultate |
Vezi soluțiile trimise | Statistici
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. |