3297 - fmi orase1

Sursa: 3297 - fmi orase1

---

Cerinţa

Suntem în anul 2050. Resursele de apă de pe planeta noastră sunt limitate din cauza schimbărilor climatice. Sistemul de stocare a apei al unui oraș a evoluat în timp, ajungându-se la o configurație flexibilă formată din n pereţi verticali paraleli p[1], p[2], ... , p[n]. Fiecare perete p[i] are forma unui dreptunghi cu înălțimea a[i] şi lăţimea de 1 km, iar oricare doi pereţi alăturaţi p[i], p[i+1] se află la distanţa de 1 km, faţă în faţă. Fiecare dintre acești pereți poate fi coborât complet, prin culisare pe verticală, iar un bazin poate fi format din oricare doi pereți p[i], p[j] (rămaşi după coborârea tuturor celorlalți) şi din pereţi laterali, care întregesc conturul de bazin. Capacitatea unui bazin este dată de produsul dintre înălţimea peretelui celui mai mic dintre cei doi p[i], p[j] din care este format bazinul şi distanța dintre aceşti doi pereți. Sistemul de stocare poate fi descris de un șir de numere naturale a[1], a[2], ... , a[n] strict pozitive, unde a[1] reprezintă înălțimea în kilometri a peretelui p[1], a[2] reprezintă înălțimea în kilometri a peretelui p[2] și așa mai departe.

Date de intrare

Fișierul de intrare fmi_orase1.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi fișierul de ieșire fmi_orase1.out va conține pe prima linie numărul rez, reprezentând capacitatea maximă de apă care poate fi stocată în acel oraș. În cazul în care datele nu respectă restricțiile, se va doar afișa pe ecran: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• 2 ⩽ n ⩽ 100
• numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 100

Exemple

Exemplul 1

fmi_orase1.in

9

1 8 6 2 5 4 8 3 7

Ecran

Datele sunt introduse corect.

fmi_orase1.out

49

Exemplul 2

fmi_orase1.in

5

101 2 3 4 5

Ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 3297 fmi orase1

def afis_capacitate_maxima_de_apa(n, a):
    rez = 0
    for i in range(n):
        for j in range(i + 1, n):
            if min(a[i], a[j]) * (j - i) > rez:
                rez = min(a[i], a[j]) * (j - i)

    with open('fmi_orase1.out', 'w') as f:
        f.write(str(rez))


def citire_conform_restrictiilor(n, a):
    if n < 2 or n > 100:
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    for element in a:
        if element >= 100 or element < 0:
            print("Datele nu corespund restricțiilor impuse.")
            exit()
    if n != len(a):
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    print("Datele sunt introduse corect.")


if __name__ == '__main__':
    with open('fmi_orase1.in', 'r') as f:
        n = int(f.readline().strip())
        a = list(map(int, f.readline().split()))
    citire_conform_restrictiilor(n, a)
    afis_capacitate_maxima_de_apa(n, a)

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția afis_capacitate_maxima_de_apa(n, a) și funcția citire_conform_restrictiilor(n, a), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 28) după citirea numărului n (linia 30) și celor n numere pe care le vom pune în șirul „a” (linia 31). Citirea se face din fișierul fmi_orase1, pe care îl putem accesa cu comanda with open('fmi_orase1.in', 'r') as f:, iar input-urile normale sunt schimbate cu f.readline().
   După ce am citit elementele, se va apela funcția citire_conform_restrictiilor(n, a) care primește doi parametri: vectorul „a” și lungimea sa, reprezentată de variabila „n”. Funcția verifică dacă lungimea vectorului n este între 2 și 100 (linia 15), dacă elementele vectorului sunt mai mici decât 100, respectiv mai mari decât 0 ca înălțimile să fie valide (liniile 18, 19), și dacă n este lungimea vectorului „a” (linia 22). Dacă oricare dintre condiții este încălcată, se va afișa pe ecran mesajul „Datele nu corespund restricțiilor impuse.” și se va ieși din program cu comanda exit(). Dacă toate condițiile sunt respectate, se va afișa pe ecran mesajul „Datele sunt introduse corect.” (linia 25) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția afis_capacitate_maxima_de_apa(n, a) care primește ca parametrii vectorul „a” și dimensiunea sa „n”. În această funcție se inițializează variabila rez, dată în problemă (vezi date de ieșire), cu 0. În continuare, funcția utilizează o buclă "for" dublă pentru a itera prin toate combinațiile distincte de două elemente din lista "a" (de la peretele i se verifică pentru toți pereții de la i+1 la n). Apoi, pentru fiecare pereche de elemente, calculează capacitatea maximă de apă care poate fi stocată între acestea. Capacitatea maximă este calculată prin înmulțirea capacității minime dintre cele două orașe și diferența dintre pozițiile lor în listă. Dacă capacitatea maximă calculată este mai mare decât valoarea precedentă a variabilei "rez", variabila "rez" este actualizată cu noua valoare a capacității maxime. După ce se termină bucla dublă și se determină capacitatea maximă de apă, funcția deschide fișierul de ieșire numit "fmi_orase1.out" și scrie variabila rez (care reprezintă capacitatea maximă de apă) în fișier folosind funcția "write" a obiectului de fișier (liniile 10, 11).