Fişierul intrare/ieşire:bvarcolaci.in, bvarcolaci.outSursăONI 2017, clasele 11-12
AutorEugenie Daniel PosdarascuAdăugată debciobanuBogdan Ciobanu bciobanu
Timp execuţie pe test3 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/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.inbvarcolaci.outExplicaţ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

Cum se trimit solutii?