Fişierul intrare/ieşire:dominant.in, dominant.outSursăOJI 2015 clasa a 8-a
AutorDan PracsiuAdăugată defrancuCristian Francu francu
Timp execuţie pe test0.3 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

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

dominant.indominant.outExplicaţii
1
100011011100
11
Secvenţa dominantă maximală este 10001101110 şi are lungimea 11.
2
100011011100
1
Secvenţa dominantă maximală este 10001101110 şi are lungimea 11.
Este o singură secvenţă dominantă maximală.
1
0000110000111
9
Secvenţa dominantă maximală are lungime 9; aceasta este 110000111.
2
10000111000
3
Secvenţa dominantă maximală are lungimea 5. Sunt trei secvenţe dominante maximale:
00111, 01110 şi 11100.
Trebuie sa te autentifici pentru a trimite solutii. Click aici