4241 - max2secv: Difference between revisions

From Bitnami MediaWiki
Flaviu (talk | contribs)
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....
 
Flaviu (talk | contribs)
No edit summary
Line 13: Line 13:


== Date de ieșire ==  
== 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:
'''"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."'''.


== Restricţii şi precizări ==
== Restricţii şi precizări ==
Line 24: Line 25:
: 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.
: 8
: 8


Line 32: Line 35:


def citire_lista():
def citire_lista():
     n = int(input())
     try:
    lista = list(map(int, input().split()))
        k = int(input())
     return lista
        n = int(input())
        lista = list(map(int, input().split()))
        p = int(input())
        return k, lista, p
     except:
        print("Datele nu corespund restrictiilor impuse.")
        return None


def rezolva(k, lista):
    try:
        # calculam dictionarul frecventelor
        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 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)
        else:
            print("Datele nu corespund restrictiilor impuse.")
    except:
         print("Datele nu corespund restrictiilor impuse.")


    # 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
         rezultat = rezolva(k, lista)
        valideaza(rezultat)


    # 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
</syntaxhighlight>
== 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.


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.


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

Revision as of 14:35, 28 April 2023

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 c, 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

Intrare
6
2 -1 3 -8 4 -5
Ieșire
Datele nu corespund restricțiilor impuse.
Datele sunt introduse correct.
8

Rezolvare

Rezolvare ver. 1

<syntaxhighlight lang="python" line>

  1. 4241 - max2secv

def citire_lista():

   try:
       k = int(input())
       n = int(input())
       lista = list(map(int, input().split()))
       p = int(input())
       return k, lista, p
   except:
       print("Datele nu corespund restrictiilor impuse.")
       return None

def rezolva(k, lista):

   try:
       # calculam dictionarul frecventelor
       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):

   try:
       if valoare is not None:
           print("Datele sunt introduse corect.")
           print(valoare)
       else:
           print("Datele nu corespund restrictiilor impuse.")
   except:
       print("Datele nu corespund restrictiilor impuse.")

if __name__ == "__main__":

   lista_intrare = citire_lista()
   if lista_intrare is not None:
       k, lista, p = lista_intrare
       rezultat = rezolva(k, lista)
       valideaza(rezultat)


</syntaxhighlight>

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.

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.

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

Î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().