0854 - Secvente1: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 33: Linia 33:
# 0854 - Secvente1
# 0854 - Secvente1


def citire():
def minim_secvente_disjuncte(n, k, arr):
    n, k = map(int, input().split())
     count = 0
    sir = list(map(int, input().split()))
     odd_count = 0
    return n, k, sir
 
def rezolvare(n, k, sir):
     secventa = []
     secvente = 0
      
      
     for i in range(n):
     for num in arr:
         if sir[i] % 2 == 0:
         if num % 2 != 0:
             continue  # Ignoram elementele pare
             odd_count += 1
        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
        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}"
    n, k = map(int, input().split())
     arr = list(map(int, input().split()))


if __name__ == '__main__':
    if not (1 <= k < n <= 100000) or any(num >= 1000000000 for num in arr):
    n, k, sir = citire()
        print("Datele nu corespund restricțiilor impuse.")
    rez = rezolvare(n, k, sir)
     else:
     if rez != -1:
         print("Datele sunt introduse corect.")
         print("Datele sunt introduse corect.")
         print(rez)
         print(minim_secvente_disjuncte(n, k, arr))
    else:
        print("Datele nu corespund restricțiilor impuse.")  




Linia 69: Linia 61:
== Expliacatie Rezolvare ==  
== 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 minim_secvente_disjuncte primește argumentele n, k, și arr.
Funcția rezolvare() primește cele trei valori citite și calculează numărul minim de secvențe necesare.
Inițializăm două variabile: count (pentru a contoriza numărul de secvențe) și odd_count (pentru a număra câte elemente impare sunt într-o secvență).
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ă.
Parcurgem lista arr și pentru fiecare element:
Incrementăm un contor de secvențe la fiecare început de secvență.
Dacă elementul este impar, creștem odd_count cu 1.
Funcția validare() compară rezultatul obținut cu cel așteptat și aruncă o excepție în cazul în care nu se potrivește.
Dacă odd_count devine mai mare decât k, înseamnă că trebuie să începem o nouă secvență, deci creștem count cu 1 și resetăm odd_count la 1.
În final, am adăugat un test pentru a verifica funcția rezolvare() și am afișat rezultatul.
Funcția returnează count + 1, deoarece ultima secvență nu va fi inclusă în numărul de secvențe contorizate.
În funcția if __name__ == "__main__": citim datele de intrare, validăm datele, apoi apelăm funcția minim_secvente_disjuncte și afișăm rezultatul.

Versiunea de la data 13 mai 2023 21:32

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

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.
4

Rezolvare

Rezolvare ver. 1

# 0854 - Secvente1

def minim_secvente_disjuncte(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__":
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))

    if not (1 <= k < n <= 100000) or any(num >= 1000000000 for num in arr):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")
        print(minim_secvente_disjuncte(n, k, arr))

Expliacatie Rezolvare

Funcția minim_secvente_disjuncte primește argumentele n, k, și arr. Inițializăm două variabile: count (pentru a contoriza numărul de secvențe) și odd_count (pentru a număra câte elemente impare sunt într-o secvență). Parcurgem lista arr și pentru fiecare element: Dacă elementul este impar, creștem odd_count cu 1. Dacă odd_count devine mai mare decât k, înseamnă că trebuie să începem o nouă secvență, deci creștem count cu 1 și resetăm odd_count la 1. Funcția returnează count + 1, deoarece ultima secvență nu va fi inclusă în numărul de secvențe contorizate. În funcția if __name__ == "__main__": citim datele de intrare, validăm datele, apoi apelăm funcția minim_secvente_disjuncte și afișăm rezultatul.

Adus de la „http://wiki.universitas.ro/index.php?title=0854_-_Secvente1&oldid=6334”