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
numere25.out: Datele sunt introduse corect.; 1 2 5 6 7 9 10

Exemplul 2

numere25.in: 10; 1 2 3 4 6 7 9
numere25.out: Datele sunt introduse corect.; 3 5 8 10

Exemplul 3

numere25.in: 5; 3 2 4 1 5
numere25.out: Datele nu corespund restricțiilor impuse.

Rezolvare

2824 - Numere 25

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]) -> None:

   """
   Afișează numerele lipsă, ordonate crescător.
   """
   if nr_lipsa:
       print(*nr_lipsa)
   else:
       print("Nu exista")

def gaseste_numere_lipsa(n: int, lst: list[int]) -> list[int]:

   """
   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.")
       return []
   nr_lipsa = []
   j = 1
   for nr in lst:
       while j < nr:
           nr_lipsa.append(j)
           j += 1
       j = nr + 1
   while j <= n:
       nr_lipsa.append(j)
       j += 1
   return nr_lipsa

Citirea datelor de intrare din fișier

with open("numere25.in", "r") as f:

   # Citim n din prima linie a fișierului și îl convertim la int
   n = int(f.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.readline().split()))

Găsirea numerelor lipsă și afișarea lor

if valideaza_intrare(n, lst):

   # Dacă datele sunt valide, afișăm un mesaj corespunzător
   print("Datele sunt introduse corect.")
   # Calculăm numerele lipsă și le afișăm
   nr_lipsa = gaseste_numere_lipsa(n, lst)
   afiseaza_lipsa(nr_lipsa)
   # Scriem rezultatele în fișierul de ieșire
   with open("numere25.out", "w") as f:
       if nr_lipsa:
           f.write(" ".join(map(str, nr_lipsa)))
       else:
           f.write("Nu exista\n")
       # Adăugăm mesajul de validare în fișierul de ieșire
       if valideaza_intrare(n, lst):
           f.write("Datele sunt introduse corect.\n")
       else:
           f.write("Datele nu corespund restricțiilor impuse.\n")
   print("Fisierul de iesire a fost creat cu succes.")

</syntaxhighlight>