2824 - Numere 25 - Revision history

Sovago Rares-Andrei at 09:13, 8 April 2023

2023-04-08T09:13:48Z

← Older revision		Revision as of 09:13, 8 April 2023
Line 115:		Line 115:

	</syntaxhighlight>		</syntaxhighlight>

			==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ă.

Nagy Lenard at 20:30, 24 March 2023

2023-03-24T20:30:38Z

← Older revision		Revision as of 20:30, 24 March 2023
Line 17:		Line 17:
	; ''numere25.in''		; ''numere25.in''
	: 10		: 10
	:3 4 4 8		: 3 4 4 8
			; ''Ecran''
			:Datele sunt introduse corect.
	; ''numere25.out''		; ''numere25.out''
	~~:Datele sunt introduse corect.~~
	:1 2 5 6 7 9 10		:1 2 5 6 7 9 10
	=== Exemplul 2 ===		=== Exemplul 2 ===
Line 25:		Line 26:
	:10		:10
	:1 2 3 4 6 7 9		:1 2 3 4 6 7 9
			; ''Ecran''
			:Datele sunt introduse corect.
	; ''numere25.out''		; ''numere25.out''
	~~:Datele sunt introduse corect.~~
	:3 5 8 10		:3 5 8 10

Line 33:		Line 35:
	:5		:5
	:3 2 4 1 5		:3 2 4 1 5
	; ''~~numere25.out~~''		; ''Ecran''
	:Datele nu corespund restricțiilor impuse.		:Datele nu corespund restricțiilor impuse.

Line 76:		Line 78:
	"""		"""
	if not valideaza_intrare(n, lst):		if not valideaza_intrare(n, lst):
	~~f.write~~("Datele nu corespund restricțiilor impuse.\n")		print("Datele nu corespund restricțiilor impuse.")
	sys.exit(1)		sys.exit(1)
	nr_lipsa = []		nr_lipsa = []
	j = 1		ultimul_nr_verificat = 1
	for nr in lst:		for nr in lst:
	while j < nr:		while ultimul_nr_verificat < nr:
	nr_lipsa.append(j)		nr_lipsa.append(ultimul_nr_verificat)
	j += 1		ultimul_nr_verificat += 1
	j = nr + 1		ultimul_nr_verificat = nr + 1
	while j <= n:		while ultimul_nr_verificat <= n:
	nr_lipsa.append(j)		nr_lipsa.append(ultimul_nr_verificat)
	j += 1		ultimul_nr_verificat += 1
	afiseaza_lipsa(nr_lipsa, f)		afiseaza_lipsa(nr_lipsa, f)


	# Citirea datelor de intrare din fișier		if __name__ == '__main__':
	with open("numere25.in", "r") as f_in, open("numere25.out", "w", encoding="utf-8") as f_out:		# Citirea datelor de intrare din fișier
	# Citim n din prima linie a fișierului și îl convertim la int		with open("numere25.in", "r") as f_in, open("numere25.out", "w", encoding="utf-8") as f_out:
	n = int(f_in.readline().strip())		# Citim n din prima linie a fișierului și îl convertim la int
	# Citim lista de numere din a doua linie a fișierului și o convertim la listă de int		n = int(f_in.readline().strip())
	lst = list(map(int, f_in.readline().split()))		# 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):~~
	~~f_out.write("Datele sunt introduse corect.\n")~~
	~~gaseste_numere_lipsa(n, lst, f_out)~~
	~~else:~~
	~~f_out.write("Datele nu corespund restricțiilor impuse.\n")~~
	~~sys.exit(1)~~





			# 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)

Sovago Rares-Andrei: /* Rezolvare */

2023-03-24T17:44:43Z

Rezolvare

← Older revision		Revision as of 17:44, 24 March 2023
Line 42:		Line 42:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 2824 - Numere 25		# 2824 - Numere 25
			import sys


	def valideaza_intrare(n: int, lst: list[int]) -> bool:		def valideaza_intrare(n: int, lst: list[int]) -> bool:
	"""		"""
Line 58:		Line 61:


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


	def gaseste_numere_lipsa(n: int, lst: list[int]) -> ~~list[int]~~:		def gaseste_numere_lipsa(n: int, lst: list[int], f) -> None:
	"""		"""
	Găsește numerele lipsă din intervalul [1, n] față de lista dată.		Găsește numerele lipsă din intervalul [1, n] față de lista dată.
	"""		"""
	if not valideaza_intrare(n, lst):		if not valideaza_intrare(n, lst):
	~~print~~("Datele nu corespund restricțiilor impuse.")		f.write("Datele nu corespund restricțiilor impuse.\n")
	~~return []~~		sys.exit(1)
	nr_lipsa = []		nr_lipsa = []
	j = 1		j = 1
Line 85:		Line 88:
	nr_lipsa.append(j)		nr_lipsa.append(j)
	j += 1		j += 1
	~~return~~ nr_lipsa		afiseaza_lipsa(nr_lipsa, f)


	# Citirea datelor de intrare din fișier		# Citirea datelor de intrare din fișier
	with open("numere25.in", "r") as f:		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		# Citim n din prima linie a fișierului și îl convertim la int
	n = int(f.readline().strip())		n = int(f_in.readline().strip())
	# Citim lista de numere din a doua linie a fișierului și o convertim la listă de int		# 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()))		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):
			f_out.write("Datele sunt introduse corect.\n")
			gaseste_numere_lipsa(n, lst, f_out)
			else:
			f_out.write("Datele nu corespund restricțiilor impuse.\n")
			sys.exit(1)



	~~# 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.")~~

Sovago Rares-Andrei: /* Exemplul 2 */

2023-03-24T17:44:20Z

Exemplul 2

← Older revision		Revision as of 17:44, 24 March 2023
Line 27:		Line 27:
	; ''numere25.out''		; ''numere25.out''
	:Datele sunt introduse corect.		:Datele sunt introduse corect.
	:5 8 10		:3 5 8 10

	===Exemplul 3===		===Exemplul 3===
	; ''numere25.in''		; ''numere25.in''

Sovago Rares-Andrei: Pagină nouă: == 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]...

2023-03-23T19:54:12Z

Pagină nouă: == 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]...

New page

== 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.
:5 8 10
===Exemplul 3===
; ''numere25.in''
:5
:3 2 4 1 5
; ''numere25.out''
:Datele nu corespund restricțiilor impuse.

<br>

== Rezolvare ==
<syntaxhighlight lang="python" line="1">
# 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>