2824 - Numere 25

Cerinţa

SSe dă un număr natural n și un șir de numere naturale din intervalul [1,n] ordonate crescător. Să se afișeze în ordine strict crescătoare toate numerele din intervalul [1,n] care nu se găsesc în șirul dat. Dacă nu există asemenea numere se afișează Nu exista.

Date de intrare

Fișierul de intrare numere25.in conține pe prima linie numărul n, iar pe a doua linie șir de numere naturale din intervalul [1,n] ordonate crescător.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran: "Datele sunt introduse corect.", Fișierul de ieșire numere25.out va conține pe prima linie în ordine strict crescătoare toate numerele din intervalul [1,n] care nu se găsesc în șirul dat. Dacă nu există asemenea numere fișierul va conține textul 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

• 1 ≤ n ≤ 107;
• în enunțul original, 1 ≤ n ≤ 109; aici limitele au fost micșorate, datorită dimensiunilor prea mari ale fișierelor de intrare/ieșire;
• proiectați un algoritm eficient din punctul de vedere al memoriei şi al timpului de executare:
• se recomandă evitarea utilizării tablourilor sau a altor structuri de date similare.

Exemple

Exemplul 1

numere25.in

10

3 4 4 8

Ecran

Datele sunt introduse corect.

numere25.out

1 2 5 6 7 9 10

Exemplul 2

numere25.in

10

1 2 3 4 6 7 9

Ecran

Datele sunt introduse corect.

numere25.out

3 5 8 10

Exemplul 3

numere25.in

5

3 2 4 1 5

Ecran

Datele nu corespund restricțiilor impuse.

Rezolvare

# 2824 - Numere 25
import sys


def valideaza_intrare(n: int, lst: list[int]) -> bool:
    """
    Verifică dacă datele de intrare sunt valide conform cerințelor.
    """
    if not (1 <= n <= 10**7) or len(lst) > n:
        return False
    for i in range(len(lst)):
        if not (1 <= lst[i] <= n):
            return False
        if i > 0 and lst[i] < lst[i-1]:
            return False
    if len(set(lst)) != len(lst):
        return False
    return True


def afiseaza_lipsa(nr_lipsa: list[int], f) -> None:
    """
    Afișează numerele lipsă, ordonate crescător.
    """
    if nr_lipsa:
        f.write(" ".join(map(str, nr_lipsa)) + "\n")
    else:
        f.write("Nu exista\n")


def gaseste_numere_lipsa(n: int, lst: list[int], f) -> None:
    """
    Găsește numerele lipsă din intervalul [1, n] față de lista dată.
    """
    if not valideaza_intrare(n, lst):
        print("Datele nu corespund restricțiilor impuse.")
        sys.exit(1)
    nr_lipsa = []
    ultimul_nr_verificat = 1
    for nr in lst:
        while ultimul_nr_verificat < nr:
            nr_lipsa.append(ultimul_nr_verificat)
            ultimul_nr_verificat += 1
        ultimul_nr_verificat = nr + 1
    while ultimul_nr_verificat <= n:
        nr_lipsa.append(ultimul_nr_verificat)
        ultimul_nr_verificat += 1
    afiseaza_lipsa(nr_lipsa, f)


if __name__ == '__main__':
    # Citirea datelor de intrare din fișier
    with open("numere25.in", "r") as f_in, open("numere25.out", "w", encoding="utf-8") as f_out:
        # Citim n din prima linie a fișierului și îl convertim la int
        n = int(f_in.readline().strip())
        # Citim lista de numere din a doua linie a fișierului și o convertim la listă de int
        lst = list(map(int, f_in.readline().split()))

        # Verificăm dacă datele sunt valide și afișăm un mesaj corespunzător în fișier
        if valideaza_intrare(n, lst):
            print("Datele sunt introduse corect.")
            gaseste_numere_lipsa(n, lst, f_out)
        else:
            print("Datele nu corespund restricțiilor impuse.")
            sys.exit(1)

Explicatie

Acest program primește ca date de intrare un număr întreg n și o listă de numere întregi lst și are ca scop să găsească numerele lipsă din intervalul [1, n] față de lista dată și să le afișeze în ordine crescătoare într-un fișier de ieșire.

Funcția valideaza_intrare verifică dacă datele de intrare respectă restricțiile impuse: n trebuie să fie cuprins între 1 și 10^7, lista lst trebuie să conțină cel mult n elemente, toate elementele listei trebuie să fie cuprinse între 1 și n și lista trebuie să fie ordonată crescător și să nu conțină duplicate.

Funcția afiseaza_lipsa primește lista de numere lipsă și un fișier de ieșire și afișează aceste numere separate prin spațiu și urmate de un caracter newline, sau stringul "Nu exista" în cazul în care nu există numere lipsă.

Funcția gaseste_numere_lipsa primește numărul n, lista lst și un fișier de ieșire și găsește numerele lipsă din intervalul [1, n] față de lista dată. Pentru aceasta, se parcurge lista lst și se compară fiecare element cu numerele de la ultimul număr verificat până la acel element. Numerele lipsă sunt adăugate la o listă separată, care este apoi afișată folosind funcția afiseaza_lipsa.

În secțiunea __main__, se citește fișierul de intrare numere25.in, se validează datele de intrare folosind funcția valideaza_intrare, se găsesc numerele lipsă folosind funcția gaseste_numere_lipsa, și apoi se scrie rezultatul în fișierul de ieșire numere25.out. În cazul în care datele nu sunt valide, se afișează un mesaj corespunzător și programul se termină.