4241 - max2secv: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
 
Linia 41: Linia 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.

Versiunea curentă din 14 mai 2023 21:18

Sursa: - 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

Dacă datele sunt introduse corect, pe ecran se va afișa: "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

  • 2 ≤ n ≤ 100.000
  • -100 ≤ a[i] ≤ 100
  • Două secvențe sunt disjuncte dacă nu au niciun element comun.

Exemplu 1

Intrare
6
2 -1 3 -8 4 -5
Ieșire
Datele sunt introduse correct.
8

Exemplu 2

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


Rezolvare

Rezolvare ver. 1

# 4241 - max2secv

def validate_input(n, nums):
    if not (2 <= n <= 100000):
        return False
    if len(nums) != n:
        return False
    if any(num < -100 or num > 100 for num in nums):
        return False
    return True

def find_max_sum(n, nums):
    if not validate_input(n, nums):
        return "Datele nu corespund restricțiilor impuse."

    max_sum = float('-inf')
    for i in range(n-1):
        sum1 = sum(nums[:i+1])
        sum2 = sum(nums[i+1:])
        max_sum = max(max_sum, sum1 + sum2)
    
    return max_sum

if __name__ == "__main__":
    n = int(input())
    nums = list(map(int, input().split()))

    result = find_max_sum(n, nums)
    print(result)

Explicatie Rezolvare

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

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

La final, funcția returnează max_sum, reprezentând suma maximă a două secvențe disjuncte.

__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.