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 "Datele de intrare nu corespund restricțiilor 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

<syntaxhighlight lang="python" line>

1. 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):

   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__':

   nr_arbori = int(input())
   inaltime_vraja = int(input())
   inaltime_arbori = []

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

       inaltime_arbori.append(inaltime)

   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)

</syntaxhighlight>