2840 - Secventa Uniforma - Revision history

Sovago Rares-Andrei at 16:41, 29 April 2023

2023-04-29T16:41:25Z

← Older revision		Revision as of 16:41, 29 April 2023
Line 30:		Line 30:
	:5 5 5 5 5 5 5 5		:5 5 5 5 5 5 5 5
	===Exemplul 3===		===Exemplul 3===
	~~=== Exemplul 2 ===~~
	; ''secventauniforma.in''		; ''secventauniforma.in''
	: 2 3 1000000001		: 2 3 1000000001

Sovago Rares-Andrei at 05:32, 15 April 2023

2023-04-15T05:32:52Z

← Older revision		Revision as of 05:32, 15 April 2023
Line 114:		Line 114:

	</syntaxhighlight>		</syntaxhighlight>

			==Explicatie==
			Funcția valideaza_intrare(lst: list[int]) -> bool verifică dacă datele de intrare sunt valide, adică:

			lista are o lungime între 2 și 10^6;
			fiecare element al listei este un număr întreg între 0 și 10^9;
			toți termenii din listă sunt egali.
			Funcția returnează True dacă datele sunt valide și False în caz contrar.

			Funcția gaseste_secventa_uniforma(lst: list[int]) -> tuple[int, list[int]] primește o listă de numere și încearcă să găsească cea mai lungă secvență uniformă din acea listă. Dacă datele de intrare nu sunt valide (conform funcției valideaza_intrare), se va returna o secvență nulă, adică o secvență cu o lungime de 0 și o listă goală de termeni.

			Dacă datele de intrare sunt valide, funcția parcurge lista și verifică dacă fiecare element este egal cu elementul anterior. Dacă da, înseamnă că am găsit un termen nou în secvență uniformă curentă, iar lungimea acesteia crește cu 1 și adăugăm termenul la lista de termeni curenti. Dacă nu, înseamnă că am găsit o secvență uniformă mai mică decât cea curentă, deci verificăm dacă lungimea ei este mai mare decât lungimea maximă găsită până acum. Dacă da, actualizăm lungimea maximă și lista de termeni maximi.

			După ce am parcurs toată lista, returnăm lungimea maximă și lista de termeni maximi.

			Funcția afiseaza_secventa_uniforma(lungime: int, termeni: list[int]) -> None primește lungimea și lista de termeni a celei mai lungi secvențe uniforme găsite și le afișează într-un fișier de ieșire numit "secventauniforma.out". Dacă datele de intrare nu sunt valide, afișează un mesaj corespunzător în locul secvenței uniforme.

			Observați că, în cadrul acestei funcții, se mai face încă o dată validarea datelor de intrare, folosind funcția valideaza_intrare(lst: list[int]) -> bool. Aceasta este o măsură de siguranță suplimentară, pentru a evita afișarea unei secvențe uniforme în cazul în care datele de intrare sunt invalide.

			În blocul if __name__ == '__main__': citim datele de intrare din fișierul "secventauniform

Nagy Lenard: /* Rezolvare */

2023-03-24T20:14:35Z

Rezolvare

← Older revision		Revision as of 20:14, 24 March 2023
Line 95:		Line 95:


	# Citirea datelor de intrare din fișier		if __name__ == '__main__':
	with open("secventauniforma.in", "r") as f:		# Citirea datelor de intrare din fișier
	# Citim lista de numere din prima linie a fișierului și o convertim la listă de int		with open("secventauniforma.in", "r") as f:
	lst = list(map(int, f.readline().split()))		# Citim lista de numere din prima linie a fișierului și o convertim la listă de int
			lst = list(map(int, f.readline().split()))

	# Găsirea secvenței uniforme și afișarea ei în fișierul de ieșire		# Găsirea secvenței uniforme și afișarea ei în fișierul de ieșire
	lungime, termeni = gaseste_secventa_uniforma(lst)		lungime, termeni = gaseste_secventa_uniforma(lst)
	afiseaza_secventa_uniforma(lungime, termeni)		afiseaza_secventa_uniforma(lungime, termeni)

Sovago Rares-Andrei: /* Rezolvare */

2023-03-24T17:57:30Z

Rezolvare

← Older revision		Revision as of 17:57, 24 March 2023
Line 44:		Line 44:
	<syntaxhighlight lang="python" line="1">		<syntaxhighlight lang="python" line="1">
	# 2840 - Secventa Uniforma		# 2840 - Secventa Uniforma
	def valideaza_intrare(~~n: int,~~ lst: list[int]) -> bool:		def valideaza_intrare(lst: list[int]) -> bool:
	"""		"""
	Verifică dacă datele de intrare sunt valide conform cerințelor.		Verifică dacă datele de intrare sunt valide conform cerințelor.
	"""		"""
	if not (1 <= n <= 10**~~7) or len(lst~~) ~~> n~~:		if not (2 <= len(lst) <= 10 ** 6):
	return False		return False
	for i in range(len(lst)):		for i in range(1, len(lst)):
	if ~~not (1~~ <= lst[i] ~~<= n)~~:		if lst[i] < 0 or lst[i] > 10 ** 9 or lst[i] != lst[i - 1]:
	return False		return False
	~~if i > 0 and lst[i] < lst[i-1]:~~
	~~return False~~
	~~if len(set(lst)) != len(lst):~~
	~~return False~~
	return True		return True


	def ~~afiseaza_lipsa~~(~~nr_lipsa~~: list[int]) -> ~~None~~:		def gaseste_secventa_uniforma(lst: list[int]) -> tuple[int, list[int]]:
	"""		"""
	~~Afișează numerele lipsă, ordonate crescător~~.		Găsește cea mai lungă secvență uniformă în șirul dat.
	"""		"""
	if ~~nr_lipsa~~:		if not valideaza_intrare(lst):
	~~print~~(*nr_lipsa)		return 0, []
	~~else~~:		lungime_maxima = 1
	~~print("Nu exista")~~		termeni_maximi = [lst[0]]
			lungime_curenta = 1
			termeni_curenti = [lst[0]]
			for i in range(1, len(lst)):
			if lst[i] == lst[i - 1]:
			lungime_curenta += 1
			termeni_curenti.append(lst[i])
			else:
			if lungime_curenta > lungime_maxima:
			lungime_maxima = lungime_curenta
			termeni_maximi = termeni_curenti
			lungime_curenta = 1
			termeni_curenti = [lst[i]]
			if lungime_curenta > lungime_maxima:
			lungime_maxima = lungime_curenta
			termeni_maximi = termeni_curenti
			return lungime_maxima, termeni_maximi


	def ~~gaseste_numere_lipsa~~(n: int, ~~lst~~: list[int]) -> ~~list[int]~~:		def afiseaza_secventa_uniforma(lungime: int, termeni: list[int]) -> None:
	"""		"""
	~~Găsește numerele lipsă din intervalul [1, n] față~~ de ~~lista dată~~.		Afișează secvența uniformă găsită în fișierul de ieșire.
	"""		"""
	if ~~not~~ valideaza_intrare(n, lst):		with open("secventauniforma.out", "w", encoding="utf-8") as f:
	~~print~~("Datele ~~nu corespund restricțiilor impuse~~.")		if valideaza_intrare(lst):
	~~return []~~		f.write("Datele sunt introduse corect.\n")
	~~nr_lipsa = []~~		f.write(str(lungime) + "\n")
	~~j = 1~~		f.write(" ".join(map(str, termeni)))
	~~for nr in lst:~~		else:
	~~while j < nr:~~		f.write("Datele nu corespund restricțiilor impuse.")
	~~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		# Citirea datelor de intrare din fișier
	with open("~~numere25~~.in", "r") as f:		with open("secventauniforma.in", "r") as f:
	~~# Citim n din prima linie a fișierului și îl convertim la int~~		# Citim lista de numere din prima linie a fișierului și o convertim la listă de 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()))		lst = list(map(int, f.readline().split()))

	# Găsirea ~~numerelor lipsă~~ și afișarea ~~lor~~		# Găsirea secvenței uniforme și afișarea ei în fișierul de ieșire
	~~if valideaza_intrare(n, lst):~~		lungime, termeni = gaseste_secventa_uniforma(lst)
	~~# Dacă datele sunt valide, afișăm un mesaj corespunzător~~		afiseaza_secventa_uniforma(lungime, termeni)
	~~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 1 */

2023-03-24T17:56:30Z

Exemplul 1

← Older revision		Revision as of 17:56, 24 March 2023
Line 16:		Line 16:
	===Exemplul 1===		===Exemplul 1===
	; ''secventauniforma.in''		; ''secventauniforma.in''
	: ~~2 3 3 3 3 5 4 4 11 11 11 11 16 11 11 11 11 15 15~~		:1 1 1 1 1 1 1 1 1 1
	; ''secventauniforma.out''		; ''secventauniforma.out''
	:Datele sunt introduse corect.		:Datele sunt introduse corect.
	:4		:10
	:~~3 3 3 3~~		:1 1 1 1 1 1 1 1 1 1

	=== Exemplul 2 ===		=== Exemplul 2 ===
	; ''secventauniforma.in''		; ''secventauniforma.in''

Sovago Rares-Andrei: Pagină nouă: == Cerinţa == Numim '''secvență uniformă''' a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași valoare, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia. Se dă un șir de cel puțin două și cel mult '''1000000''' de numere naturale din intervalul '''[0,10^9]'''. În șir există cel puțin doi termeni egali pe poziții consecutive. Se cere să se determine o secvență...

2023-03-23T20:15:59Z

Pagină nouă: == Cerinţa == Numim '''secvență uniformă''' a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași valoare, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia. Se dă un șir de cel puțin două și cel mult '''1000000''' de numere naturale din intervalul '''[0,10^9]'''. În șir există cel puțin doi termeni egali pe poziții consecutive. Se cere să se determine o secvență...

New page

== Cerinţa ==
Numim '''secvență uniformă''' a unui șir de numere naturale un subșir al acestuia, format din termeni cu aceeași valoare, aflați pe poziții consecutive în șirul dat. Lungimea secvenței este egală cu numărul de termeni ai acesteia.

Se dă un șir de cel puțin două și cel mult '''1000000''' de numere naturale din intervalul '''[0,10^9]'''. În șir există cel puțin doi termeni egali pe poziții consecutive. Se cere să se determine o secvență uniformă de lungime maximă în șirul dat și să se afișeze pe lungimea acestei secvențe și termenii acesteia. Dacă sunt mai multe astfel de secvențe, se afișează doar termenii ultimei dintre acestea.
== Date de intrare ==
Fișierul de intrare '''secventauniforma.in''' conține pe prima linie un șir de cel puțin două și cel mult '''1000000''' de numere naturale din intervalul '''[0,10^9]''', separate prin spații.
== Date de ieșire ==
Dacă datele sunt introduse corect, pe ecran:
"Datele sunt introduse corect.",fișierul de ieșire '''secventauniforma.out''' va conține pe prima linie lungimea acestei secvențe și, pe o linie nouă, separați prin câte un spațiu, termenii acesteia.. Î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 numerelor cerute se utilizează un algoritm eficient din punctul de vedere al memoriei necesare și al timpului de executare.
*Se recomandă evitarea memorării elementelor șirului într-un tablou sau în altă structură de date similară.

== Exemple ==
===Exemplul 1===
; ''secventauniforma.in''
: 2 3 3 3 3 5 4 4 11 11 11 11 16 11 11 11 11 15 15
; ''secventauniforma.out''
:Datele sunt introduse corect.
:4
:3 3 3 3
=== Exemplul 2 ===
; ''secventauniforma.in''
: 5 5 5 5 5 5 5 5
; ''secventauniforma.out''
:Datele sunt introduse corect.
:8
:5 5 5 5 5 5 5 5
===Exemplul 3===
=== Exemplul 2 ===
; ''secventauniforma.in''
: 2 3 1000000001
; ''iesire''
:Datele nu corespund restricțiilor impuse.
; ''secventauniforma.out''

<br>

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