Fişierul intrare/ieşire:mate.in, mate.outSursăLot Bistrita 2009, Baraj 3
AutorAdrian AirineiAdăugată deandrei-alphaAndrei-Bogdan Antonescu andrei-alpha
Timp execuţie pe test0.85 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Mate

Testele pentru aceasta problema nu sunt destul de bine construite pentru a departaja corect solutii ineficiente sau gresite.
Intra aici daca vrei sa ne ajuti sa imbunatatim calitatea testelor pentru aceasta problema!

Mirunel, fratele Mirunei, a dezvoltat o adevarată pasiune pentru matematică. Jucându-se cu şiruri de numere naturale, a întalnit o problemă pentru care abilităţile sale de matematician nu sunt suficiente. El a descoperit un şir S format din N numere naturale cuprinse între 1 şi N şi trebuie să determine lungimea cea mai mare a unei subsecvenţe care conţine un element majoritar. Într-o subsecvenţă de lungime L, un element este majoritar dacă apare de cel puţin [(L+1)/2] ori (partea întreagă a lui (L+1)/2 ).

Cerinta

Determinaţi lungimea maximă a unei subsecvenţe care conţine un element majoritar.

Date de intrare

Fişierul de intrare mate.in va conţine pe prima linie un singur număr natural, N, având semnificaţia din enunţ. Pe urmatoarea linie se află N numere naturale separate printr-un singur spaţiu, reprezentând şirul de numere.

Date de ieşire

Fişierul de ieşire mate.out va conţine un singur număr natural, reprezentând lungimea maximă a unei subsecvenţe care conţine un element majoritar.

Restricţii

  • 1 ≤ N ≤ 500.000
  • 1 ≤ Si ≤ N

Exemplu

mate.inmate.out
5
4 1 1 2 3
4
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content