Editing 0854 - Secvente1

Sursa: [https://www.pbinfo.ro/probleme/854/secvente1 0854 - Secvente1]
----
== Cerinţa ==
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 ==
Programul citește de la tastatură numerele n k, iar apoi cele n elemente ale șirului

== Date de ieșire == 
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 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.


== Rezolvare == 
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 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 == 

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.