Problema: Dominant / 
Autor: Considerând un șir de valori binare, numim secvență dominantă un set de elemente aflate pe poziții consecutive în șir care are proprietatea că numărul valorilor egale cu 1 este strict mai mare decât numărul valorilor de 0. De exemplu, în șirul 1,0,0,0,1,1,0,1,1,1,0,0 o secvență dominantă este 0,1,1 și o alta, de lungime mai mare, este 0,1,1,0,1,1,1. Secvența dominantă maximală este secvența dominantă de lungime maximă. În șirul din exemplu secvența dominantă maximală este 1,0,0,0,1,1,0,1,1,1,0 (adică întreg șirul, fără ultimul zero).
Cerinţă
Dat fiind un șir de valori binare, să se determine lungimea unei secvențe dominante maximale precum și numărul acestor secvențe.
Date de intrare
Fișierul de intrare dominant.in conține pe prima linie un număr natural V, iar pe linia a doua șirul de valori binare, fără spații.
Date de ieșire
Fișierul de ieșire dominant.out va conține:
- varianta 1: dacă
V=1, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând lungimea unei secvențe dominante maximale. - varianta 2: dacă
V=2, atunci pe prima linie a fișierului de ieșire va fi un singur număr natural reprezentând numărul secvențelor dominante maximale.
Restricții și precizări
Vpoate fi1sau2- Lungimea șirului de valori binare este de cel mult
300 000. - Pentru toate testele șirul binar va conține cel puțin o valoare de
1. - Pentru 60% din punctaj
V = 1.
Exemplul 1
dominant.in
1 100011011100
dominant.out
11
Explicație
Secvența dominantă maximală este 10001101110 și are lungimea 11.
Exemplul 2
dominant.in
2 100011011100
dominant.out
1
Explicație
Secvența dominantă maximală este 10001101110 și are lungimea 11. Este o singură secvență dominantă maximală.
Exemplul 3
dominant.in
1 0000110000111
dominant.out
9
Explicație
Secvența dominantă maximală are lungime 9; aceasta este 110000111.
Exemplul 4
dominant.in
2 10000111000
dominant.out
3
Explicație
Secvența dominantă maximală are lungimea 5. Sunt trei secvențe dominante maximale: 00111, 01110 și 11100.
