0165 - maxsim

Sursa: 0165 - maxsim

---

Cerinţa

Se dau n numere naturale reprezentând elementele unui vector. Să se determine perechea de elemente egal depărtate de centru pentru care suma valorilor este maximă. Dacă sunt mai multe perechi cu suma maximă se va determina perechea cea mai apropiată de capete.

Date de intrare

Fişierul de intrare maxsim.in conţine pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spaţii, reprezentând elementele vectorului.

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 maxsim.out va conţine pe prima linie trei numere S, i, j, separate prin exact un spațiu, reprezentând suma maximă obținută și pozițiile elementelor din pereche. În cazul în care datele nu respectă restricțiile, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse."'.

Restricţii şi precizări

• 0 < n ≤ 1000
• numerele de pe a doua linie a fişierului de intrare vor fi mai mici decât 1.000.000.000
• elementele vectorului se consideră numerotate de la 1
• 1 ≤ i < j ≤ n

Exemple

Exemplul 1

maxsim.in

7

6 2 5 4 3 6 1

Ecran

Datele sunt introduse corect.

maxsim.out

8 2 6

Exemplul 2

elempp.in

5

5 3 2 4

Ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 0165

def afis_perechea_elem_egal_departate_cu_sum_max(n, vector):
    S = -1
    i = -1
    j = -1
    for k in range(1, n // 2 + 1):
        if vector[k - 1] + vector[n - k] > S:
            S = vector[k - 1] + vector[n - k]
            i = k
            j = n - k + 1
    with open('maxsim.out', 'w') as fisier_iesire:
        fisier_iesire.write(str(S) + " " + str(i) + " " + str(j))


def citire_conform_restrictiilor(n, vector):
    if n < 1 or n > 1000:
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    for element in vector:
        if element >= 1000000000:
            print("Datele nu corespund restricțiilor impuse.")
            exit()
    if n != len(vector):
        print("Datele nu corespund restricțiilor impuse.")
        exit()
    print("Datele sunt introduse corect.")


if __name__ == '__main__':
    with open('maxsim.in', 'r') as fisier_intrare:
        n = int(fisier_intrare.readline().strip())
        vector = list(map(int, fisier_intrare.readline().strip().split()))
    citire_conform_restrictiilor(n, vector)
    afis_perechea_elem_egal_departate_cu_sum_max(n, vector)

Explicație rezolvare

   Programul de mai sus conține două funcții, funcția afis_perechea_elem_egal_departate_cu_sum_max(n, vector) și funcția citire_conform_restrictiilor(n, vector), care se vor rula în interiorul main-ului (if __name__ == '__main__' , linia 30) după citirea numărului n (linia 32) și celor n numere pe care le vom pune în șirul „vector” (linia 33), pe care le citim prin deschiderea fișierului maxsim.in (linia 35).
   După ce am citit toate datele de intrare, se va apela funcția citire_conform_restrictiilor(n, vector) care primește doi parametri: n și vector. Funcția verifică n între 0 și 1000 (linia 17), dacă elementele vectorului „vector” sunt mai mici decât 1000000000 (liniile 20-21) și dacă n este lungimea vectorului „vector” (linia 24). 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 mesajul „Datele sunt introduse corect.” (linia 27) și se va continua programul.
   Dacă s-au introdus corect datele, se va apela funcția afis_perechea_elem_egal_departate_cu_sum_max(n, vector) care primește ca parametrii numărul n și vectorul „vector”. Mai exact, funcția parcurge vectorul vector de la început până la jumătate (folosind o buclă for care merge de la 1 până la n // 2 + 1, linia 7). Pentru fiecare pereche de elemente egal depărtate de centru, se calculează suma valorilor acestora (vector[k - 1] + vector[n - k]) și se compară cu valoarea maximă curentă (S). Dacă suma valorilor pentru o pereche de elemente este mai mare decât maximul curent (S), se actualizează suma maximă (S) și se rețin pozițiile elementelor în variabilele i și j. Aceste poziții reprezintă poziția elementului din stânga și poziția elementului din dreapta, în perechea de elemente cu suma maximă. La final, valorile maximului (S) și pozițiilor elementelor (i și j) sunt scrise în fișierul de ieșire "maxsim.out" folosind funcția write() a unui obiect de fișier deschis în modul de scriere ('w').