4241 - max2secv - Revision history

Flaviu at 21:18, 14 May 2023

2023-05-14T21:18:28Z

← Older revision		Revision as of 21:18, 14 May 2023
Line 41:		Line 41:
	# 4241 - max2secv		# 4241 - max2secv

	def ~~citire_lista~~():		def validate_input(n, nums):
	~~try:~~		if not (2 <= n <= 100000):
	k = ~~int(input())~~		return False
	n = ~~int(input()~~)		if len(nums) != n:
	~~lista = list(map(int, input().split~~()))		return False
	p = ~~int(input())~~		if any(num < -100 or num > 100 for num in nums):
	return ~~k, lista, p~~		return False
	~~except~~:		return True
	~~print("Datele nu corespund restrictiilor impuse.")~~
	return ~~None~~

	def ~~rezolva~~(k, ~~lista~~):		def find_max_sum(n, nums):
	~~try:~~		if not validate_input(n, nums):
	~~# calculam dictionarul frecventelor~~		return "Datele nu corespund restricțiilor impuse."
	~~frecvente = {}~~
	~~for element in lista:~~
	~~frecvente[element] = frecvente.get(element, 0) + 1~~

	~~# gasim elementul cu cea mai mare frecventa~~
	~~max_frecventa = max(frecvente.values())~~
	~~element_max_frecventa = max(k for k, v in frecvente.items()~~ if ~~v == max_frecventa)~~

	~~# calculam lungimea maxima a unui platou dupa k operatii~~
	~~lungime_maxima = min~~(~~max_frecventa + k~~, ~~len(lista)~~)
	return ~~lungime_maxima if p == 1 else element_max_frecventa~~
	~~except:~~
	~~print(~~"Datele nu corespund ~~restrictiilor~~ impuse.")
	~~return None~~

	~~def valideaza~~(~~valoare~~):		max_sum = float('-inf')
	~~try~~:		for i in range(n-1):
	~~if valoare is not None~~:		sum1 = sum(nums[:i+1])
	~~print("Datele sunt introduse corect."~~)		sum2 = sum(nums[i+1:])
	~~print~~(~~valoare~~)		max_sum = max(max_sum, sum1 + sum2)
	~~else:~~
	~~print~~(~~"Datele nu corespund restrictiilor impuse."~~)		return max_sum
	~~except:~~
	~~print("Datele nu corespund restrictiilor impuse.")~~

	if __name__ == "__main__":		if __name__ == "__main__":
	~~lista_intrare~~ = ~~citire_lista~~()		n = int(input())
	~~if lista_intrare is not None:~~		nums = list(map(int, input().split()))
	~~k, lista, p = lista_intrare~~
	~~rezultat~~ = ~~rezolva~~(k, ~~lista~~)		result = find_max_sum(n, nums)
	~~valideaza~~(~~rezultat~~)		print(result)


	</syntaxhighlight>		</syntaxhighlight>
	== Explicatie Rezolvare ==		== Explicatie Rezolvare ==
	~~citire_lista~~(): ~~această~~ funcție ~~încearcă să citească o listă de întregi~~ și ~~două valori întregi k~~ și p de ~~la tastatură~~. Dacă ~~citirea~~ este ~~corectă~~, funcția returnează k, lista și p. ~~În caz contrar, afișează un mesaj~~ de ~~eroare "Datele nu corespund restrictiilor impuse."~~ și ~~returnează None~~.		validate_input(n, nums): Această funcție primește numărul n și lista nums și verifică dacă datele de intrare sunt valide în conformitate cu restricțiile cerinței. Verificările efectuate sunt:

			Verifică dacă n se află în intervalul [2, 100000]. Dacă nu, funcția returnează False.
			Verifică dacă lungimea listei nums este egală cu n. Dacă nu, funcția returnează False.
			Verifică dacă există cel puțin un element în lista nums care nu se încadrează în intervalul [-100, 100]. Dacă da, funcția returnează False.
			Dacă toate verificările sunt îndeplinite, funcția returnează True, semnalând că datele sunt valide.
			find_max_sum(n, nums): Această funcție primește numărul n și lista nums și determină suma maximă care se poate obține din două secvențe disjuncte din șir. Funcția inițializează max_sum cu o valoare extrem de mică (pentru a permite compararea și actualizarea corectă).

	~~rezolva(k~~, ~~lista): această funcție primește două argumente: k~~ (~~un întreg~~) și ~~lista~~ (~~o listă de întregi~~). ~~Scopul acestei funcții~~ este ~~să găsească lungimea maximă a unui platou după k operații. Un platou~~ este o secvență de elemente consecutive egale din lista dată. Operațiile sunt de două tipuri: (1) adăugarea unui element la lista dată, (2) eliminarea unui element din lista dată. Funcția încearcă să calculeze elementul din lista cu cea mai mare ~~frecvență și să găsească lungimea maximă a unui platou după k operații~~. ~~Dacă p = 1, funcția returnează elementul cu cea mai mare frecvență~~, ~~altfel returnează lungimea~~ maximă ~~a unui platou~~.		Apoi, folosind o buclă for de la 0 la n-2, se calculează suma primelor i+1 elemente (sum1) și suma ultimelor n-i-1 elemente (sum2). Suma acestor două secvențe este calculată ca sum1 + sum2, iar rezultatul este actualizat dacă această sumă este mai mare decât max_sum. Astfel, se determină suma maximă posibilă.

	~~valideaza(valoare): această funcție primește o valoare (fie un întreg~~, ~~fie o listă de întregi) și afișează un mesaj "Datele sunt introduse corect." și valoarea dată pe un rând separat. Dacă valoarea dată nu este un întreg sau o listă de întregi~~, ~~afișează un mesaj de eroare "Datele nu corespund restrictiilor impuse."~~.		La final, funcția returnează max_sum, reprezentând suma maximă a două secvențe disjuncte.

	~~În secțiunea principală a codului, se citesc datele~~ de intrare ~~folosind funcția citire_lista()~~ și ~~se apelează funcția rezolva() cu argumentele corespunzătoare. Apoi, rezultatul este validat cu funcția valideaza()~~.		__main__: Această secțiune verifică dacă scriptul este executat direct (nu importat ca modul) și conține citirea datelor de intrare de la tastatură și apelarea funcției find_max_sum.

Flaviu at 07:54, 3 May 2023

2023-05-03T07:54:59Z

← Older revision		Revision as of 07:54, 3 May 2023
Line 14:		Line 14:
	== Date de ieșire ==		== Date de ieșire ==
	Dacă datele sunt introduse corect, pe ecran se va afișa:		Dacă datele sunt introduse corect, pe ecran se va afișa:
	'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul c''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.		'''"Datele sunt introduse corect."''', apoi pe un rând nou '''numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte''', reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: '''"Datele nu corespund restricțiilor impuse."'''.

	== Restricţii şi precizări ==		== Restricţii şi precizări ==
Line 20:		Line 20:
	* -100 ≤ a[i] ≤ 100		* -100 ≤ a[i] ≤ 100
	* Două secvențe sunt disjuncte dacă nu au niciun element comun.		* Două secvențe sunt disjuncte dacă nu au niciun element comun.
	== Exemplu ==		== Exemplu 1 ==
	; Intrare		; Intrare
	: 6		: 6
	: 2 -1 3 -8 4 -5		: 2 -1 3 -8 4 -5
	; Ieșire		; Ieșire
	~~: Datele nu corespund restricțiilor impuse.~~
	: Datele sunt introduse correct.		: Datele sunt introduse correct.
	: 8		: 8

			== Exemplu 2 ==
			; Intrare
			: 1 2 3
			: 77
			; Ieșire
			: Datele nu corespund restricțiilor impuse.


	== Rezolvare ==		== Rezolvare ==

Flaviu at 14:35, 28 April 2023

2023-04-28T14:35:06Z

@@ Line 13: / Line 13: @@
 == Date de ieșire ==
-Programul va afișa pe ecran numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte.
+Dacă datele sunt introduse corect, pe ecran se va afișa:
 == Restricţii şi precizări ==
@@ Line 24: / Line 25: @@
 : 2 -1 3 -8 4 -5
 ; Ieșire
 : 8
@@ Line 32: / Line 35: @@
 def citire_lista():
-     n = int(input())
+     try:
-    lista = list(map(int, input().split()))
+        k = int(input())
-     return lista
+        n = int(input())
-def suma_maxima(lista):
+def valideaza(valoare):
-     # Calculăm suma maximă a unei secvențe care se termină în fiecare poziție
+     try:
-    sume_maxime_stanga = [lista[0]]
+        if valoare is not None:
-    for i in range(1, len(lista)):
+            print("Datele sunt introduse corect.")
-         sume_maxime_stanga.append(max(lista[i], sume_maxime_stanga[i-1]+lista[i]))
+            print(valoare)
-    # Calculăm suma maximă a unei secvențe care începe din fiecare poziție
+if __name__ == "__main__":
-     sume_maxime_dreapta = [lista[-1]]
+     lista_intrare = citire_lista()
-     for i in range(len(lista)-2, -1, -1):
+     if lista_intrare is not None:
-         sume_maxime_dreapta.insert(0, max(lista[i], sume_maxime_dreapta[0]+lista[i]))
+        k, lista, p = lista_intrare
-    return suma_maxima
+</syntaxhighlight>
-def validare(lista, suma_maxima):
+valideaza(valoare): această funcție primește o valoare (fie un întreg, fie o listă de întregi) și afișează un mesaj "Datele sunt introduse corect." și valoarea dată pe un rând separat. Dacă valoarea dată nu este un întreg sau o listă de întregi, afișează un mesaj de eroare "Datele nu corespund restrictiilor impuse.".
-Funcția suma_maxima(lista) determină suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. Pentru aceasta, calculează suma maximă a unei secvențe care se termină în fiecare poziție a șirului și suma maximă a unei secvențe care începe din fiecare poziție a șirului, folosind metoda Kadane. Apoi, determină suma maximă dintre două secvențe disjuncte din șir, parcurgând
+În secțiunea principală a codului, se citesc datele de intrare folosind funcția citire_lista() și se apelează funcția rezolva() cu argumentele corespunzătoare. Apoi, rezultatul este validat cu funcția valideaza().

Flaviu: Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4241/max2secv - max2secv] ---- Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj. == Cerinţa == Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații....

2023-04-17T20:49:38Z

Pagină nouă: Sursa: [https://www.pbinfo.ro/probleme/4241/max2secv - max2secv] ---- Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj. == Cerinţa == Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. == Date de intrare == Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații....

New page

Sursa: [https://www.pbinfo.ro/probleme/4241/max2secv - max2secv]
----
Se dă un șir a1, a2, …, an de numere întregi. Definim suma unei secvențe ai, ai+1, …, aj ca fiind suma elementelor sale, adică ai + ai+1 + ... + aj.

== Cerinţa ==
Să se determine suma maximă posibilă care se poate obține din două secvențe disjuncte din șir.

== Date de intrare ==
Programul citește de la tastatură numărul n, iar apoi șirul de n numere întregi, separate prin spații.

== Date de ieșire ==
Programul va afișa pe ecran numărul S, reprezentând suma maximă care se poate obține din două secvențe disjuncte.

== Restricţii şi precizări ==
* 2 ≤ n ≤ 100.000
* -100 ≤ a[i] ≤ 100
* Două secvențe sunt disjuncte dacă nu au niciun element comun.
== Exemplu ==
; Intrare
: 6
: 2 -1 3 -8 4 -5
; Ieșire
: 8

== Rezolvare ==
=== Rezolvare ver. 1 ===
<syntaxhighlight lang="python" line>
# 4241 - max2secv

def citire_lista():
n = int(input())
lista = list(map(int, input().split()))
return lista

def suma_maxima(lista):
# Calculăm suma maximă a unei secvențe care se termină în fiecare poziție
sume_maxime_stanga = [lista[0]]
for i in range(1, len(lista)):
sume_maxime_stanga.append(max(lista[i], sume_maxime_stanga[i-1]+lista[i]))

# Calculăm suma maximă a unei secvențe care începe din fiecare poziție
sume_maxime_dreapta = [lista[-1]]
for i in range(len(lista)-2, -1, -1):
sume_maxime_dreapta.insert(0, max(lista[i], sume_maxime_dreapta[0]+lista[i]))

# Determinăm suma maximă dintre cele două secvențe disjuncte
suma_maxima = sume_maxime_stanga[-1] # suma întregului șir
for i in range(len(lista)-1):
suma_maxima = max(suma_maxima, sume_maxime_stanga[i]+sume_maxime_dreapta[i+1])

return suma_maxima

def validare(lista, suma_maxima):
# verificăm că suma maximă poate fi obținută din două secvențe disjuncte
for i in range(1, len(lista)):
# verificăm că suma maximă a unei secvențe care se termină în i este mai mică sau egală decât suma maximă a unei secvențe care se termină în i-1
if sum(lista[:i]) <= sum(lista[:i-1]):
continue
for j in range(i+1, len(lista)):
# verificăm că suma maximă a unei secvențe care începe din j este mai mică sau egală decât suma maximă a unei secvențe care începe din j+1
if sum(lista[j:]) <= sum(lista[j+1:]):
continue
if sum(lista[:i]) + sum(lista[j:]) == suma_maxima:
return True
return False

if __name__ == "__main__":
lista = citire_lista()
s = suma_maxima(lista)
if validare(lista, s):
print(s)
else:
print("Nu se poate obține suma maximă din două secvențe disjuncte.")

</syntaxhighlight>
== Explicatie Rezolvare ==
Funcția citire_lista() primește șirul de numere de la tastatură și îl returnează sub formă de listă.

Funcția suma_maxima(lista) determină suma maximă posibilă care se poate obține din două secvențe disjuncte din șir. Pentru aceasta, calculează suma maximă a unei secvențe care se termină în fiecare poziție a șirului și suma maximă a unei secvențe care începe din fiecare poziție a șirului, folosind metoda Kadane. Apoi, determină suma maximă dintre două secvențe disjuncte din șir, parcurgând