4240 - Nr Secv 01

Cerință

Scrieți funcția cu următorul antet:

 long long NrSecv01(const char s[])

Funcția primește ca parametru un șir format doar din 0 și 1 și returnează numărul se secvențe care conțin exact un caracter 1.

Date de intrare

un șir de caractere s, format din caracterele 0 'și 1, cu o lungime maximă de 200.000.

Date de ieșire

un număr întreg de tip long long, reprezentând numărul de secvențe care conțin exact un caracter 1.

Restricții de precizări

Lungimea șirului s va fi de cel mult 200.000.
Puteți utiliza funcțiile pentru șirurile de caractere din biblioteca cstring

Exemplu

Exemplul 1

NrSecv01("0101") = 6, secvențele care conțin exact un 1 fiind: 01, 010, 1, 10, 01, 1.

Important

Soluţia propusă va conţine doar definiţia subprogramului cerut. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.

Rezolvare

Rezolvare var. 1

def NrSecv01(s: str) -> int:

   n = len(s)
   count = 0
   ones = 0
   for i in range(n):
       if s[i] == '1':
           ones += 1
       elif ones == 1:
           count += 1
       elif ones > 1:
           count += ones*(ones-1)//2
           ones = 0
   if ones == 1:
       count += 1
   elif ones > 1:
       count += ones*(ones-1)//2
   return count

def validate_input(s: str) -> bool:

   if len(s) > 200000:
       return False
   for c in s:
       if c not in {'0', '1'}:
           return False
   return True

if __name__ == '__main__':

   s = input().strip()
   if not validate_input(s):
       print("Input invalid")
   else:
       print(NrSecv01(s))

</syntaxhighlight>

Explicație

Funcția NrSecv01 primește un șir de caractere s și folosește o variabilă count pentru a număra secvențele care conțin exact un caracter '1'. Variabila ones numără câte '1' consecutivi există în șirul s, iar atunci când se întâlnește un caracter '0', se verifică dacă există exact un caracter '1' în secvența anterioară (reprezentată de variabila ones). Dacă da, se incrementează count. În cazul în care există mai mult de un '1' consecutiv, se calculează numărul de perechi de '1' care pot fi formate și se adaugă la count. La final, se mai verifică o dată dacă există exact un '1' în ultima secvență și se adaugă la count dacă este cazul.

Funcția validate_input verifică dacă șirul de intrare respectă restricțiile impuse: lungimea maximă este de 200.000, iar șirul trebuie să conțină doar caracterele '0' și '1'.

În programul principal, se citește șirul de la tastatură și se validează. Dacă șirul nu este valid, se afișează un mesaj corespunzător, altfel se apelează funcția NrSecv01 și se afișează rezultatul.