2827 - Sir 12

Cerinţa

Se consideră un șir de cel mult 10^6 numere naturale distincte din intervalul [1,10^9]. Se cere să se determine cei mai mari doi termeni pari din șir care sunt precedați de doar trei termeni impari.

Date de intrare

Fișierul de intrare sir12.in conține pe prima termenii șirului, separați prin câte un spațiu.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.",Fișierul de ieșire sir12.out va conține pe prima linie termenii determinați, în ordine strict crescătoare, separați printr-un spațiu, iar dacă în șir nu există doi astfel de termeni, se afișează mesajul Nu exista. În cazul în care datele nu respectă restricțiile, se va afișa: "Datele nu corespund restricțiilor impuse.".

Restricţii şi precizări

• Pentru determinarea și afișarea numerelor cerute se utilizează un algoritm eficient din punctul de vedere al spațiului de memorie și al timpului de executare;
• Se recomandă evitarea memorării numerelor într-un tablou sau în altă structură de date similară

Exemple

Exemplul 1

sir12.in

4 3 5 312 27 30 14 212 11 15 17 400

ecran

Datele sunt introduse corect.

sir12.out

30 212

Exemplul 2

sir12.in

1 3 5 7 9 11

ecran

Datele sunt introduse corect.

sir12.out

Nu exista

Exemplul 3

sir12.in

1 2 3 4 5 6 -1

ecran

Datele nu corespund restricțiilor impuse.

sir12.out

(Nu se scrie niciun rezultat în fișierul de ieșire pentru acest exemplu, deoarece datele de intrare nu sunt valide.)

Rezolvare

# 2827 - Sir 12
import sys

def valideaza_datele_intrare(sequenta):
    if len(sequenta) > 1000000 or any(n < 1 or n > 1000000000 for n in sequenta):
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(0)
    print("Datele sunt introduse corect.")

def gaseste_maxime_pare_precedati_de_3_impare(sequenta):
    cnt = 0
    max1, max2 = -1, -1
    for n in sequenta:
        if n % 2 == 1:
            cnt += 1
        elif cnt == 3:
            if n > max1:
                max2 = max1
                max1 = n
            elif n > max2:
                max2 = n
    if max1 != -1 and max2 != -1:
        return max2, max1
    else:
        return None

if __name__ == "__main__":
    with open("sir12.in") as fin, open("sir12.out", "w") as fout:
        # citeste datele de intrare
        sequenta = list(map(int, fin.readline().split()))

        # valideaza datele de intrare
        valideaza_datele_intrare(sequenta)

        # gaseste cei mai mari doi termeni pari
        maxime_pare = gaseste_maxime_pare_precedati_de_3_impare(sequenta)
        if maxime_pare is not None:
            fout.write(f"{maxime_pare[0]} {maxime_pare[1]}")
        else:
            fout.write("Nu exista")

Explicatie

Valideaza_datele_intrare(sequenta): această funcție primește ca argument o secvență de numere întregi și verifică dacă aceasta corespunde restricțiilor impuse. În caz contrar, afișează un mesaj de eroare și oprește execuția programului prin apelarea funcției sys.exit(0). În cazul în care secvența de numere respectă restricțiile, afișează un mesaj de confirmare.

Gaseste_maxime_pare_precedati_de_3_impare(sequenta): această funcție primește ca argument o secvență de numere întregi și caută cei mai mari doi termeni pari care sunt precedați de cel puțin 3 termeni impari în secvență. Dacă astfel de termeni există, funcția returnează cei doi termeni maxim pari găsiți în ordine descrescătoare. În caz contrar, funcția returnează valoarea None.

Funcțiile sunt apoi utilizate în funcția principală main(), care citeste datele de intrare dintr-un fișier și scrie rezultatele într-un alt fișier. În cazul în care datele de intrare nu respectă restricțiile impuse, programul se va opri înainte de a apela funcția gaseste_maxime_pare_precedati_de_3_impare(sequenta). Dacă datele sunt corecte, programul va apela funcția gaseste_maxime_pare_precedati_de_3_impare(sequenta) și va scrie rezultatul în fișierul de ieșire.