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

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

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

# Iesirea dacă restricțiile nu sunt îndeplinite
if not verificare_restrictii(n, []):
    exit()

# Citirea elementelor șirului
arr = list(map(int, input("Introduceti elementele separate prin spatii: ").split()))

# Iesirea dacă restricțiile nu sunt îndeplinite
if not verificare_restrictii(n, arr):
    exit()

# Calculul numărului de elemente impare
rezultat = numar_elemente_impare(arr, 0, n - 1)

# Afișarea rezultatului
print(rezultat)