1018 - Cnt Impare

Cerința

Se consideră un șir cu n elemente, numere naturale. Folosind metoda Divide et Impera, determinați câte elemente impare sunt în acest șir.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi cele n elemente ale șirului.

Date de ieșire

Programul va afișa pe ecran numărul C, reprezentând valoarea cerută.

Restricții și precizări

• 1 ≤ n ≤ 1000
• elementele șirului vor fi mai mici decât 1.000.000
• se recomandă folosirea metodei Divide et Impera

Exemplul 1

Intrare

6
4 1 8 4 3 5 

Ieșire

3

Exemplul 2

Intrare

1001

Ieșire

Eroare: Numărul de elemente trebuie să fie între 1 și 1000.

Rezolvare

<syntaxhighlight lang="python3" line="1"> def verificare_restrictii(n, arr):

   # Verifică restricția 1: 1 ≤ n ≤ 1000
   if not (1 <= n <= 1000):
       print("Eroare: Numărul de elemente trebuie să fie între 1 și 1000.")
       return False

   # Verifică restricția 2: Elementele șirului vor fi mai mici decât 1.000.000
   if any(x >= 1000000 for x in arr):
       print("Eroare: Elementele șirului trebuie să fie mai mici decât 1.000.000.")
       return False

   return True

def numar_elemente_impare(arr, stanga, dreapta):

   if stanga == dreapta:
       return arr[stanga] % 2

   mijloc = (stanga + dreapta) // 2

   # Numără elementele impare în stânga și dreapta
   impare_stanga = numar_elemente_impare(arr, stanga, mijloc)
   impare_dreapta = numar_elemente_impare(arr, mijloc + 1, dreapta)

   # Combină rezultatele
   return impare_stanga + impare_dreapta

1. Exemplu de folosire

n = int(input("Introduceti numarul de elemente: "))

1. Iesirea dacă restricțiile nu sunt îndeplinite

if not verificare_restrictii(n, []):

   exit()

1. Citirea elementelor șirului

arr = list(map(int, input("Introduceti elementele separate prin spatii: ").split()))

1. Iesirea dacă restricțiile nu sunt îndeplinite

if not verificare_restrictii(n, arr):

   exit()

1. Calculul numărului de elemente impare

rezultat = numar_elemente_impare(arr, 0, n - 1)

1. Afișarea rezultatului

print(rezultat) </syntaxhighlight>