3499 - Secv011

Sursa: - Secv011

---

Cerinţa

Se dă un șir A format din n elemente din mulțimea {0,1}. Numim secvență a șirului A orice succesiune de elemente situate pe poziții consecutive în șir. Numim secvență a șirului A orice succesiune de elemente situate pe poziții consecutive în șir. Să se determine numărul de secvențe ale șirului A ce conțin de două ori mai mulți de 1 decât de 0.

Date de intrare

Pe prima linie a fișierului secv011.in se află numărul n. Pe următoarea linie se află cele n elemente ale șirului , separate prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt corecte.", iar apoi in fișierul de ieșire secv011.out va conține pe prima linie numărul cerut. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000

Exemple

Exemplul 1

secv011.in

6

1 0 1 1 1 0

Ieșire

Datele sunt corecte.

secv011.out

4

Exemplul 2

secv011.in

10

1 0 0 0 1 1 1 0 0 0

Ieșire

Datele sunt corecte.

secv011.out

2

Exemplul 3

secv011.in

2

314441 41241241

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 0302 Secv011

def secv011(vector,n):

   f = open("secv011.out","w")
   contor = 0 
   zero = 0 
   unu = 0 
   for i in range(n):
       for j in range(i,n):
           if vector[j] == 0:
               zero += 1
           else:
               unu +=1
           if unu > 1 and unu == 2 * zero:
               contor += 1
       zero = 0
       unu = 0
   f.write(str(contor))
   
   

def conform_restrictiilor():

   with open('secv011.in') as f:
       n = int(f.readline().strip())
       vector = list(map(int, f.read().split()))
   if not 1 <= n <= 100000:
       print("Datele nu sunt conform restricțiilor impuse.")
       exit()
   for x in vector:
       if x > 1:
           print("Datele nu sunt conform restricțiilor impuse.")
           exit()
   print("Datele sunt corecte.")
   return n, vector 

if __name__ == '__main__':

   n, vector= conform_restrictiilor()
   secv011(vector,n)

</syntaxhighlight>

Explicaţie cod

Acesta este un program care citeste un vector de numere intregi din fisierul secv011.in, verifica daca exista secvente de cel putin doua cifre 1 consecutive, separate de o secventa de cifre 0 si afiseaza numarul total de astfel de secvente in fisierul secv011.out.

Functia conform_restrictiilor() citeste datele de intrare din fisierul secv011.in si verifica daca sunt conforme cu restrictiile impuse. In cazul in care acestea nu sunt conforme, se afiseaza un mesaj de eroare si programul se termina. Daca datele sunt conforme, functia returneaza vectorul vector si lungimea acestuia n.

Functia secv011(vector, n) calculeaza numarul de secvente valide din vector. Pentru fiecare subsecventa a vectorului, numara cate cifre 0 si cate cifre 1 sunt prezente si verifica daca exista o secventa de cel putin doua cifre 1 consecutive, separate de o secventa de cifre 0. Daca exista, incrementarea contorului contor. La final, functia afiseaza valoarea contorului in fisierul secv011.out.