Editing 0839 - Vraja2 (section)

==Rezolvare==
<syntaxhighlight lang="python" line="1">
 
def calc_nr_vraj(copaci, idx):
    # Verificam in stanga pana la primul copac cu inaltime mai mare
    for i in range(idx-1, -1, -1):
        if copaci[i] > copaci[idx]:
            return idx - i
    # Daca nu am gasit copac mai mare in stanga, cautam in dreapta
    for i in range(idx+1, len(copaci)):
        if copaci[i] > copaci[idx]:
            return i - idx
    # Daca nu am gasit copac mai mare nici in stanga nici in dreapta
    return 0


def rezolvare(n, copaci):
    nr_vraj = 0
    for i in range(n):
        nr_vraj += calc_nr_vraj(copaci, i)
    return nr_vraj


def validare(n, copaci):
    if not (2 <= n <= 10**5):
        return False
    for h in copaci:
        if not (1 <= h <= 10**9):
            return False
    return True


def main():
    n = int(input("Introduceti numarul n: "))
    copaci = []
    for i in range(n):
        inaltime = int(input(f"Introduceti inaltimea copacului {i+1}: "))
        copaci.append(inaltime)

    if validare(n, copaci):
        print("Datele de intrare corespund restrictiilor")
        nr_vraj = rezolvare(n, copaci)
        print(f"Numarul minim de vraji necesare este: {nr_vraj}")
    else:
        print("Datele de intrare nu corespund cerintei")


if __name__ == '__main__':
    main()

</syntaxhighlight>