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

# 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")


# 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.")