0398 - Plopi 2

Cerinţa

De-a lungul principalei străzi din orașul nostru există n plopi, pentru fiecare cunoscându-se înălțimea. Primarul orașului dorește ca plopii să aibă înălțimile în ordine descrescătoare. Pentru aceasta, este posibilă tăierea dintr-un plop a unei bucăți – este o tehnică ecologică, nevătămătoare, în urma căreia plopul nu are de suferit. Plopii nu pot fi înălțați în niciun fel.

Determinați numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Date de intrare

Fișierul de intrare plopi2in.txt conține pe prima linie numărul de plopi n. Urmează n numere naturale nenule, separate prin spaţii, care pot fi dispuse pe mai multe linii, reprezentând înălțimile plopilor.

Date de ieşire

Fișierul de ieșire plopi2out.txt va conține pe prima linie numerele C T, separate prin exact un spațiu, reprezentând numărul minim de plopi din care se va tăia și lungimea totală minimă a bucăților tăiate.

Restricții și precizări

• 2 ⩽ n ⩽ 100
• înălțimile plopilor vor fi mai mici decât 10000

Exemplul 1

plopi2in.txt

8
5 7 3 6 4 4 2 6

plopi2out.txt

Datele de intrare corespund restrictiilor impuse.
5 11

Explicație

Vom tăia din plopii numerotați cu 2 4 5 6 8, astfel încât înălțimile să devină 5 5 3 3 3 3 2 2. Lungimea totală a bucăților tăiate este: 2 + 3 + 1 + 1 +4 = 11

Exemplul 2

plopi2in.txt

yrteofmnrf

plopi2out.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. Funcția de validare verifică dacă datele de intrare sunt în intervalul specificat

def validare(n_validare, inaltimi_validare):

   # Verificăm dacă n este în intervalul 2-100
   if n_validare < 2 or n_validare > 100:
       raise ValueError  # Ridicăm o eroare dacă n nu este în intervalul 2-100
   for inaltime in inaltimi_validare:    # Parcurgem lista de înălțimi
       # Verificăm dacă înălțimea este mai mică decât 10000
       if inaltime >= 10000:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse.\n")

1. Funcția taie_plopi taie plopii astfel încât să aibă înălțimile în ordine descrescătoare

def taie_plopi(n_taie, inaltimi_taie):

   # Inițializăm numărul de plopi din care se va tăia și lungimea totală a bucăților tăiate
   nr_plopi, lungime_totala = 0, 0
   # Parcurgem lista de înălțimi
   for i in range(1, n_taie):
       # Dacă înălțimea plopului curent este mai mare decât înălțimea plopului anterior
       if inaltimi_taie[i] > inaltimi_taie[i-1]:
           # Tăiem din plop
           lungime_totala += inaltimi_taie[i] - inaltimi_taie[i-1]
           inaltimi_taie[i] = inaltimi_taie[i-1]
           nr_plopi += 1
   return nr_plopi, lungime_totala

if __name__ == '__main__':

   file_in = open("plopi2in.txt", "r")
   file_out = open("plopi2out.txt", "w")

   try:
       # Citim numărul de plopi
       n_main = int(file_in.readline())
       # Citim înălțimile plopilor
       inaltimi_main = list(map(int, file_in.readline().split()))
       # Validăm datele de intrare
       validare(n_main, inaltimi_main)
       # Tăiem plopii
       nr_plopi_main, lungime_totala_main = taie_plopi(n_main, inaltimi_main)
       # Scriem numărul de plopi din care se va tăia și lungimea totală a bucăților tăiate în fișierul de ieșire
       file_out.write(str(nr_plopi_main) + ' ' + str(lungime_totala_main) + '\n')

   # Dacă datele de intrare nu sunt valide, afișăm un mesaj de eroare
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")
   # Dacă datele de intrare sunt incomplete, afișăm un mesaj de eroare
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse.")

</syntaxhighlight>