0854 - Secvente1

Sursa: 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

Programul va afișa pe ecran numărul minim de secvențe C.

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

Intrare

7 2

4 3 4 9 9 1 8

Ieșire

2

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

1. 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):

   secventa = []
   secvente = 0
   
   for i in range(n):
       if sir[i] % 2 == 0:
           continue  # Ignoram elementele pare
       if len(secventa) == 0 or len(secventa[-1]) == k:
           secventa.append([sir[i]])  # Cream o secventa noua
           secvente += 1
       else:
           secventa[-1].append(sir[i])  # Adaugam elementul la ultima secventa
       
   return secvente

def validare(secvente, rezultat):

   assert secvente == rezultat, f"Secvente: {secvente}, Rezultat asteptat: {rezultat}"

if __name__ == '__main__':

   # Teste
   n, k, sir = citire()
   rez = rezolvare(n, k, sir)
   validare(rez, 2)  # Pentru sirul [3, 9, 9, 1] avem 2 secvente de lungime maxima k=2
   print(rez)

</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 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ă. 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 final, am adăugat un test pentru a verifica funcția rezolvare() și am afișat rezultatul.