0839 - Vraja2

Cerința

De-a lungul bulevardului sunt n copaci, numerotați de la 1 la n, pentru fiecare cunoscându-se înălțimea, exprimată în centimetri. Primarul dorește să taie copacii și apelează la un vrăjitor care va proceda astfel: alege o secvență cât mai lungă de copaci învecinați și aplică o vrajă prin care toți înălțimea tuturor copacilor din secvență scade cu o aceeași valoare, strict pozitivă.

Să se determine care este numărul minim de vrăji care trebuie aplicate astfel încât toți copacii să aibă înălțime zero.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, reprezentând înălțimile copacilor.

Date de ieșire=

Dacă datele de intrare corespund restrictiilor impuse se va afișa mesajul "Datele de intrare corespund restricțiilor" și pe un rând nou se afișează ceea ce se cere. Altfel, dacă datele de intrare nu corespund cerinței se va afișa mesajul: "Datele de intrare nu corespund cerinței".

Restricții și precizări

• 1 ≤ n ≤ 1000
• înălțimile arborilor sunt numere naturale nenule mai mici decât 1.000.000
• secvența aleasă de vrăjitor la un moment dat nu poate conține copaci de înălțime zero

Exemplu

Exemplu 1

Intrare:

Introduceti primul numar

3

Introduceti al doilea numar

0

Iesire:

Datele de intrare corespund restrictiilor

Numarul de moduri de a ajunge la scorul 3-0 este 1

Exemplu 2

Intrare:

Introduceti numarul n

0

Iesire:

Datele de intrare nu corespund cerintei

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>

Explicații

Codul este structurat astfel:

1. 1 validare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și verifică dacă datele de intrare respectă restricțiile problemei. În caz contrar, returnează False.

1. 2 rezolvare(n, copaci): o funcție care primește ca argumente numărul de copaci și o listă cu înălțimile lor și calculează numărul minim de vrajitori necesari pentru a proteja toți copacii. În prima buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu primul. În a doua buclă se calculează numărul minim de vrajitori necesari pentru a proteja copacii începând cu ultimul. Rezultatul final este minimul dintre cele două valori. Dacă nu este posibil să se protejeze toți copacii, funcția returnează un mesaj de eroare.

1. 3 main(): funcția principală care primește datele de intrare și afișează rezultatul. În cazul în care datele de intrare nu sunt valide, afișează un mesaj de eroare.

Datele de intrare sunt citite prin intermediul funcției input() și sunt stocate într-o listă numită copaci. Pentru a calcula numărul minim de vrajitori necesari, se parcurg toți copacii și se verifică dacă fiecare copac este protejat de vrajitorii anteriori. Dacă nu este protejat, se adaugă un nou vrajitor și se protejează copacul curent.

Rezultatul final este afișat prin intermediul funcției print(). Dacă nu este posibil să se protejeze toți copacii, se afișează un mesaj de eroare.