0603 - Vraja

Cerința

De-a lungul bulevardului sunt nr_arbori arbori, numerotați de la 0 la nr_arbori - 1, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește ca înălțimile arborilor să fie în ordine descrescătoare, și pentru aceasta apelează la vrăjitorul angajat al primăriei, care, pentru un anumit arbore poate să facă o vrajă astfel încât arborele să crească cu inaltime_vraja centimetri. Determinați numărul minim de vrăji necesare ca înălțimile arborilor să fie în ordine descrescătoare.

Date de intrare

Programul citește de la tastatură numerele nr_arbori inaltime_vraja, iar apoi nr_arbori numere naturale, reprezentând înălțimile arborilor.

Date de ieșire

Pe ecran se va afișa mesajul: "Datele de intrare corespund restricțiilor impuse". În următorul rând se va afișa pe ecran numărul num_vraji, reprezentând numărul de vrăji necesare.

În cazul în care datele introduse de la tastatură nu îndeplinesc cerințele enunțate, pe ecran se va afișa mesajul "Nu au fost respectate cerintele impuse".

Restricții și precizări

• 1 ⩽ nr_arbori ⩽ 1000
• 1 ⩽ inaltime_vraja ⩽ 1000
• înălțimile arborilor sunt numere naturale nenule mai mici decât 1000000

Exemplu 1

Intrare

4

2

2

3

3

4

Ieșire

Datele de intrare corespund restricțiilor impuse

4

Exemplu 2

Intrare

0

2

Ieșire

Nu au fost respectate cerintele impuse

Rezolvare

# 0603 - Vraja
def validare(nr_arbori, inaltime_vraja, inaltime_arbori):
    # Daca datele sunt invalide v-om face raise la eroarea ValueError

    conditii = (
        nr_arbori >= 1, nr_arbori <= 1000,
        inaltime_vraja >= 1, inaltime_vraja <= 1000
    )

    if not all(conditii):
        raise ValueError

    for inaltime in inaltime_arbori:
        if (not (inaltime > 0 and inaltime < 1000000)):
            raise ValueError


def vraja(nr_arbori, inaltime_vraja, inaltime_arbori):
    # Vom parcurge arborii în ordine inversă și vom determina pentru fiecare
    # arbore câte vrăji trebuie să i se aplice pentru a deveni cel puțin
    # la fel de înalt ca următorul.

    # Pentru aceasta, vom determina diferența de înălțime dintre cei doi
    # arbori și vom afla numărul de vrăji necesare împărțind diferența la h.

    # Apoi vom actualiza înălțimea copacului curent.
    num_vraji = 0

    for i in range(nr_arbori - 2, -1, -1):
        if inaltime_arbori[i] < inaltime_arbori[i+1]:
            diferenta = inaltime_arbori[i+1] - inaltime_arbori[i]
            nr_vraja = diferenta // inaltime_vraja
            if (nr_vraja * inaltime_vraja < diferenta):
                nr_vraja += 1
            num_vraji += nr_vraja
            inaltime_arbori[i] += nr_vraja * inaltime_vraja

    print(num_vraji)


if __name__ == '__main__':
    # Citim de la tastatura numerele cerute
    nr_arbori = int(input())
    inaltime_vraja = int(input())
    inaltime_arbori = []

    for i in range(nr_arbori):
        inaltime = int(input())

        inaltime_arbori.append(inaltime)

    # Verificam daca datele introduse sunt valide
    # daca nu afisam mesajul corespunsador
    try:
        validare(nr_arbori, inaltime_vraja, inaltime_arbori)
    except ValueError:
        print("Nu au fost respectate cerintele impuse")
    else:
        print("Datele de intrare corespund restricțiilor impuse")

        vraja(nr_arbori, inaltime_vraja, inaltime_arbori)