| Fişierul intrare/ieşire: | bvarcolaci.in, bvarcolaci.out | Sursă | ONI 2017, clasele 11-12 |
| Autor | Eugenie Daniel Posdarascu | Adăugată de |  Bogdan Ciobanu •bciobanu |
| Timp execuţie pe test | 1.5 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Bvarcolaci
Se pare că toate ideile mari care s-au înscripţionat pe vecie în inima Umanităţii au trebuit să se înfăţişeze lumii întâi cu măşti monstruoase şi terifiante.
(Friedrich Nietzsche)
Se dă un vector cu N elemente. Să se precizeze câte subsecvenţe ale acestuia admit element majoritar.
Date de intrare
Fişierul bvarcolaci.in conţine pe prima linie numărul natural N, iar pe a doua linie cele N elemente ale vectorului, separate prin câte un spaţiu.
Date de ieşire
Fişierul bvarcolaci.out va conţine pe prima linie numărul subsecvenţelor care admit element majoritar.
Restricţii
- 1 ≤ N ≤ 250.000
- Toate valorile din vector sunt cuprinse între 1 şi N
- O subsecvenţă este un subşir de elemente care apar pe poziţii consecutive în şirul iniţial. Subsecvenţele sunt definite unic de indicii primului şi ultimului element din subsecvenţă în şirul initial.
- O valoare este element majoritar al unui vector cu K elemente dacă apare de cel puţin [K/2]+1 ori în vector, unde prin [x] am notat partea întreagă a lui x.
Exemplu
| bvarcolaci.in | bvarcolaci.out | Explicaţie |
|---|---|---|
| 6 1 2 1 2 3 2 | 10 | Fiecare subsecvenţă de câte un element are element majoritar. Celelalte subsecvenţe sunt: 1 2 1 2 3 2 1 2 1 2 3 2 1 2 1 2 3 2 1 2 1 2 3 2 |
Trebuie sa te autentifici pentru a trimite solutii. Click aici
