Fișierul intrare/ieșire	dominant.in, dominant.out	Sursă	OJI 2015 clasa a 8-a
Autor	Dan Pracsiu	Adăugată de	Cristian Frâncu • francu
Timp de execuție pe test	0.3 sec	Limită de memorie	32768 KB
Scorul tău	N/A	Dificultate	2

Poți vedea testele pentru această problemă accesând atașamentele .

Vezi soluțiile trimise | Statistici

Dominant (clasa a 8-a)

Notă: testele au fost punctate ușor diferit față de original din cauza limitărilor sistemului de evaluare.

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 ∈ {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