0854 - Secvente1: Difference between revisions

Latest revision as of 20:15, 14 May 2023

Cerinţa[edit | edit source]

Se dă un șir cu n elemente, numere naturale și un număr k. Determinați numărul minim de secvențe disjuncte în care trebuie împărțit șirul astfel încât fiecare element al șirului să aparțină unei secvențe și fiecare secvență să conțină cel mult k elemente impare.

Date de intrare[edit | edit source]

Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale șirului

Date de ieșire[edit | edit source]

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou va afișa pe ecran numărul minim de secvențe C, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări[edit | edit source]

1 ≤ k < n ≤ 100.000
cele n numere citite vor fi mai mici decât 1.000.000.000

Exemplu 1[edit | edit source]

Intrare: 7 2; 4 3 4 9 9 1 8
Ieșire: Datele sunt introduse corect.; 2

Exemplu 2[edit | edit source]

Intrare: 7 2; 2 3 4 9 1 1 8
Ieșire: Datele nu corespund restricțiilor impuse.

Rezolvare[edit | edit source]

Rezolvare ver. 1[edit | edit source]

0854 - Secvente1

def validare_date_intrare(n, k, arr):

   if not (1 <= k < n <= 100000):
       return False
   if any(num >= 1000000000 for num in arr):
       return False
   return True

def rezolvare_problema(n, k, arr):

   count = 0
   odd_count = 0

   for num in arr:
       if num % 2 != 0:
           odd_count += 1

       if odd_count > k:
           count += 1
           odd_count = 1

   return count + 1

if __name__ == "__main__":

   t = int(input())

   for i in range(t):
       n, k = map(int, input().split())
       arr = list(map(int, input().split()))

       if not validare_date_intrare(n, k, arr):
           print("Datele nu corespund restricțiilor impuse.")
       else:
           print("Datele sunt introduse corect.")
           print(rezolvare_problema(n, k, arr))

</syntaxhighlight>

Expliacatie Rezolvare[edit | edit source]

Funcția validare_date_intrare verifică dacă datele de intrare respectă restricțiile problemei și returnează True dacă acestea sunt corecte, False altfel.

Funcția rezolvare_problema primește cele 3 argumente și aplică algoritmul descris în cerință pentru a determina numărul minim de secvențe disjuncte care conțin cel puțin k numere impare.

În funcția if __name__ == "__main__", se citește numărul de seturi de date, apoi pentru fiecare set de date citesc datele de intrare. Se validează datele de intrare folosind funcția validare_date_intrare și se afișează rezultatul folosind funcția rezolvare_problema.

@@ Line 7: / Line 7: @@
 == Date de ieșire ==
-Programul va afișa pe ecran numărul minim de secvențe C.
+Dacă datele sunt introduse corect, pe ecran se va afișa:
+'''"Datele sunt introduse corect."''', apoi pe un rând nou '''va afișa pe ecran numărul minim de secvențe C''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.
 == Restricţii şi precizări ==
 * 1 ≤ k < n ≤ 100.000
 * cele n numere citite vor fi mai mici decât 1.000.000.000
-== Exemplu ==
+== Exemplu 1 ==
 ; Intrare
 : 7 2
 : 4 3 4 9 9 1 8
 ; Ieșire
+: Datele sunt introduse corect.
 : 2
+== Exemplu 2 ==
+; Intrare
+: 7 2
+: 2 3 4 9 1 1 8
+; Ieșire
+: Datele nu corespund restricțiilor impuse.
@@ Line 24: / Line 32: @@
 <syntaxhighlight lang="python" line>
 # 0854 - Secvente1
-def citire():
-    n, k = map(int, input().split())
-    sir = list(map(int, input().split()))
-    return n, k, sir
-def rezolvare(n, k, sir):
+def validare_date_intrare(n, k, arr):
-     secventa = []
+     if not (1 <= k < n <= 100000):
-     secvente = 0
+        return False
+    if any(num >= 1000000000 for num in arr):
-     for i in range(n):
+        return False
-         if sir[i] % 2 == 0:
+    return True
-             continue  # Ignoram elementele pare
-         if len(secventa) == 0 or len(secventa[-1]) == k:
-             secventa.append([sir[i]])  # Cream o secventa noua
+def rezolvare_problema(n, k, arr):
-            secvente += 1
+     count = 0
-        else:
+     odd_count = 0
-             secventa[-1].append(sir[i])  # Adaugam elementul la ultima secventa
+     for num in arr:
-     return secvente
+         if num % 2 != 0:
+             odd_count += 1
+         if odd_count > k:
+             count += 1
+             odd_count = 1
+     return count + 1
-def validare(secvente, rezultat):
+if __name__ == "__main__":
-     assert secvente == rezultat, f"Secvente: {secvente}, Rezultat asteptat: {rezultat}"
+     t = int(input())
-if __name__ == '__main__':
+    for i in range(t):
-    # Teste
+        n, k = map(int, input().split())
-    n, k, sir = citire()
+        arr = list(map(int, input().split()))
-    rez = rezolvare(n, k, sir)
-    validare(rez, 2)  # Pentru sirul [3, 9, 9, 1] avem 2 secvente de lungime maxima k=2
+        if not validare_date_intrare(n, k, arr):
-    print(rez)
+            print("Datele nu corespund restricțiilor impuse.")
+        else:
+            print("Datele sunt introduse corect.")
+            print(rezolvare_problema(n, k, arr))
 </syntaxhighlight>
 == Expliacatie Rezolvare ==
-Am definit mai întâi funcția citire() care citește numerele de la tastatură și returnează cele trei valori sub forma unei tuple.
+Funcția validare_date_intrare verifică dacă datele de intrare respectă restricțiile problemei și returnează True dacă acestea sunt corecte, False altfel.
-Funcția rezolvare() primește cele trei valori citite și calculează numărul minim de secvențe necesare.
-Iterăm prin șir și construim secvențe de elemente impare care au cel mult k elemente. Pentru fiecare secvență, verificăm dacă mai putem adăuga elemente impare la ea sau trebuie să începem o secvență nouă.
+Funcția rezolvare_problema primește cele 3 argumente și aplică algoritmul descris în cerință pentru a determina numărul minim de secvențe disjuncte care conțin cel puțin k numere impare.
-Incrementăm un contor de secvențe la fiecare început de secvență.
-Funcția validare() compară rezultatul obținut cu cel așteptat și aruncă o excepție în cazul în care nu se potrivește.
+În funcția if __name__ == "__main__", se citește numărul de seturi de date, apoi pentru fiecare set de date citesc datele de intrare. Se validează datele de intrare folosind funcția validare_date_intrare și se afișează rezultatul folosind funcția rezolvare_problema.
-În final, am adăugat un test pentru a verifica funcția rezolvare() și am afișat rezultatul.