1152 - Verificare Ordonat Div Imp

Cerinta

Se dă un vector cu n elemente numere naturale. Folosind metoda Divide et Impera să se verifice dacă are elementele ordonate crescător.

Date de intrare

Programul citește de la tastatură numărul n, apoi n numere naturale, reprezentând elementele vectorului.

Date de iesire

Programul afișează pe ecran mesajul DA, dacă vectorul are elementele ordonate crescător, sau NU, în caz contrar.

Restrictii si precizari

1 ≤ n ≤ 500

fiecare element al vectorului va avea cel mult patru cifre

Exemplu

Date de intrare

7

4 5 7 9 9 10 12

Date de iesire

DA

Rezolvare

def are_elemente_ordonate_crescator(arr):

    if len(arr) <= 1:

        return True

    mijloc = len(arr) // 2

    stanga = arr[:mijloc]

    dreapta = arr[mijloc:]

    return are_elemente_ordonate_crescator(stanga) and are_elemente_ordonate_crescator(dreapta) and stanga[-1] <= dreapta[0]

def main():

    n = int(input("Introduceți lungimea vectorului: "))

    vector = list(map(int, input("Introduceți elementele vectorului separate prin spațiu: ").split()))

    rezultat = are_elemente_ordonate_crescator(vector)

    if rezultat:

        print("DA")

    else:

        print("NU")

if __name__ == "__main__":

    main()