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 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
V ia valori din mulţimea {1,2}
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
Exemplu
dominant.in
dominant.out
Explicaţii
1
100011011100
11
Secvenţa dominantă maximală este 10001101110 şi are lungimea 11.
dominant.in
dominant.out
Explicaţii
2
100011011100
1
Secvenţa dominantă maximală este 10001101110 şi are lungimea 11. Este o singură secvenţă dominantă maximală.
dominant.in
dominant.out
Explicaţii
1
0000110000111
9
Secvenţa dominantă maximală are lungime 9; aceasta este 110000111.
dominant.in
dominant.out
Explicaţii
2
10000111000
3
Secvenţa dominantă maximală are lungimea 5. Sunt trei secvenţe dominante maximale: 00111, 01110 şi 11100.