1804 - ursulet: Diferență între versiuni

De la Universitas MediaWiki
Fără descriere a modificării
Fără descriere a modificării
Linia 27: Linia 27:
: -5 0 3 1 -4 2
: -5 0 3 1 -4 2
; Ieșire
; Ieșire
: Datele sunt introduse correct.
: ursulet.out
: ursulet.out
: Datele sunt introduse correct.
: 4
: 4
: 2 4
: 2 4
Linia 38: Linia 38:
: 0.23 0 1 1 4.76 -1 -2  
: 0.23 0 1 1 4.76 -1 -2  
; Ieșire
; Ieșire
: ursulet.out
: Datele nu corespund restricțiilor impuse.
: Datele nu corespund restricțiilor impuse.


Linia 47: Linia 46:
# 1804 - ursulet
# 1804 - ursulet


def read_input():
def validare_altitudini(altitudini):
    n = int(input())
     for altitudine in altitudini:
    altitudes = list(map(int, input().split()))
         if not (-1000 <= altitudine <= 1000):
    return altitudes
             return False
 
    return True
def find_maximum_subarray(altitudes):
    max_sum = float('-inf')
    current_sum = 0
    start_index = 0
    end_index = -1
    current_start_index = 0
 
     for i in range(len(altitudes)):
        current_sum += altitudes[i]
 
         if current_sum > max_sum:
            max_sum = current_sum
            start_index = current_start_index
            end_index = i
 
        if current_sum < 0:
             current_sum = 0
            current_start_index = i + 1


    return max_sum, start_index, end_index


def write_output(result):
def obos_max(altitudini):
     max_sum, start_index, end_index = result
     suma_oboseala = 0
     with open('ursulet.out', 'w') as f:
    obos_maxim = 0
         f.write(str(max_sum) + '\n')
    inceput = 0
         f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')
    sfarsit = 0
    index = 0
   
     for i in range(len(altitudini)):
         suma_oboseala += altitudini[i]
       
         if suma_oboseala < 0:
            suma_oboseala = 0
            index = i + 1
        elif suma_oboseala > obos_maxim:
            obos_maxim = suma_oboseala
            inceput = index
            sfarsit = i
           
    return (obos_maxim, inceput + 1, sfarsit + 1)


def validate_output(expected_output, actual_output):
    with open(expected_output, 'r') as f:
        expected_values = f.readlines()
    actual_values = actual_output.strip().split('\n')
    return expected_values == actual_values


if __name__ == '__main__':
if __name__ == '__main__':
     altitudes = read_input()
     with open('ursulet.in', 'r') as f:
    result = find_maximum_subarray(altitudes)
        n = int(f.readline())
    write_output(result)
        altitudini = list(map(int, f.readline().split()))
 
   
     if validate_output('ursulet.ok', 'ursulet.out'):
     if not validare_altitudini(altitudini):
        print("Datele nu corespund restricțiilor impuse.")
    else:
         print("Datele sunt introduse corect.")
         print("Datele sunt introduse corect.")
    else:
        oboseala_max, inceput, sfarsit = obos_max(altitudini)
         print("Datele nu corespund restricțiilor impuse.")
         with open('ursulet.out', 'w') as f:
 
            f.write(str(oboseala_max) + '\n')
            f.write(str(inceput) + ' ' + str(sfarsit) + '\n')


</syntaxhighlight>
</syntaxhighlight>
== Explicatie Rezolvare ==
== Explicatie Rezolvare ==
Acest cod definește o funcție `read_input()` care citește un număr întreg `n` de la intrare și o listă de numere întregi `altitudes` separate prin spații. Lista de altitudini reprezintă altitudinile succesive ale unui traseu și reprezintă datele de intrare pentru a afla cea mai mare sumă a unei subsecvențe din traseu. Funcția returnează lista de altitudini.
În funcția validare_altitudini(altitudini) se verifică dacă toate valorile altitudinilor îndeplinesc condițiile impuse de problema (sunt numere întregi între -1000 și 1000). Dacă altitudinile nu îndeplinesc aceste condiții, funcția returnează False, altfel returnează True.
 
Funcția `find_maximum_subarray(altitudes)` primește lista de altitudini și găsește subsecvența cu cea mai mare sumă. Pentru a face acest lucru, se utilizează o abordare de tip "divide and conquer" care parcurge lista și calculează suma subsecvențelor succesive. Se actualizează maximumul și indicii începutului și sfârșitului subsecvenței cu cea mai mare sumă de fiecare dată când se găsește o sumă mai mare decât maximul actual. Dacă suma curentă scade sub zero, subsecvența curentă este abandonată și se începe o nouă subsecvență la poziția următoare. Funcția returnează o tuplă care conține suma maximă, indicele de început și indicele de sfârșit ai subsecvenței cu suma maximă.


Funcția `write_output(result)` primește rezultatul găsit de `find_maximum_subarray(altitudes)` și îl scrie într-un fișier numit 'ursulet.out', pe două linii separate. Prima linie conține suma maximă a subsecvenței, iar a doua linie conține indicii de început și sfârșit ai subsecvenței cu suma maximă, separate printr-un spațiu.
În funcția obos_max(altitudini) se parcurg altitudinile în ordine și se calculează obosiala maximă acumulată de Ursuleț pe o porțiune de zone consecutive. Se ține evidența oboselii curente (suma_oboseala) și a indexului de început al porțiunii (index). Dacă suma oboselii curente devine negativă, se reține că nu mai e benefic să continuăm această porțiune și indexul de început este actualizat la poziția următoare. Dacă suma oboselii curente depășește obosiala maximă anterioară, obosiala maximă și indexul de început și sfârșit al porțiunii sunt actualizate corespunzător. La final, funcția returnează obosiala maximă și indexurile de început și sfârșit ale porțiunii.


În funcția `main`, lista de altitudini este citită cu ajutorul `read_input()`, apoi funcția `find_maximum_subarray(altitudes)` este apelată pentru a găsi subsecvența cu suma maximă. Rezultatul este scris într-un fișier cu ajutorul `write_output(result)`.
În blocul if __name__ == '__main__': se citesc datele de intrare din fișierul ursulet.in. Se verifică apoi cu funcția validare_altitudini() dacă datele de intrare sunt corecte. Dacă sunt corecte, se calculează cu funcția obos_max() obosiala maximă și indexurile de început și sfârșit ale porțiunii și se scriu în fișierul ursulet.out. Dacă datele de intrare nu sunt corecte, se afișează un mesaj corespunzător.

Versiunea de la data 14 mai 2023 21:56

Sursa: 1804 - ursulet


Ursuleţul Grizzlyuță a plecat la drum prin Ţara Ursuleţilor. El are de parcurs zone de diferite altitudini, care sunt numere întregi. Atunci când trece dintr-o zonă în alta oboseala ursuleţului creşte cu o valoare egală cu altitudinea zonei în care trece. Pentru că drumul este prea lung, şi-a chemat prietena, pe domnişoara Lupita, pentru a îl ajuta. Aceasta i-a promis că îl va transporta cu maşina ei de-a lungul zonelor în care acesta acumulează oboseală maximă.

Cerinţa

Să se determine zonele în care Lupita îl transportă pe ursuleţul Grizzlyuță.


Date de intrare

Fișierul de intrare ursulet.in conține pe prima linie numărul N, ce semnifică numărul de zone traversate de ursuleţ. Pe linia următoare se află N numere întregi, altitudinile zonelor.


Date de ieșire

Fișierul de ieșire ursulet.out va conține: Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect.", apoi pe un rând nou pe prima linie un număr întreg ce semnifică oboseală maximă acumulată de ursuleţ pe o porţiune de zone consecutive. Pe a doua linie se află două numere, indicii primei şi ultimei zone din drumul parcurs de Lupita şi Grizzlyuță, reprezentând valoarea cerută. În cazul contrar, se va afișa pe ecran: "Datele nu corespund restricțiilor impuse.".


Restricţii şi precizări

  • 1 ≤ n ≤ 100.000
  • -1000 ≤ a ≤ 1000, a fiind altitudinea unei zone
  • Dacă există mai multe subsecvenţe candidate la soluţie, atunci se va tipări cea cu indicele de început cel mai mic, iar în caz de egalitate, cea mai scurtă.ă cu elemente ordonate crescător este maximală dacă adăugând la secvență încă un element ea nu mai are elementele ordonate crescător

Exemplu 1

Intrare
ursulet.in
6
-5 0 3 1 -4 2
Ieșire
Datele sunt introduse correct.
ursulet.out
4
2 4

Exemplu 2

Intrare
ursulet.in
6
0.23 0 1 1 4.76 -1 -2
Ieșire
Datele nu corespund restricțiilor impuse.


Rezolvare

Rezolvare ver. 1

# 1804 - ursulet

def validare_altitudini(altitudini):
    for altitudine in altitudini:
        if not (-1000 <= altitudine <= 1000):
            return False
    return True


def obos_max(altitudini):
    suma_oboseala = 0
    obos_maxim = 0
    inceput = 0
    sfarsit = 0
    index = 0
    
    for i in range(len(altitudini)):
        suma_oboseala += altitudini[i]
        
        if suma_oboseala < 0:
            suma_oboseala = 0
            index = i + 1
        elif suma_oboseala > obos_maxim:
            obos_maxim = suma_oboseala
            inceput = index
            sfarsit = i
            
    return (obos_maxim, inceput + 1, sfarsit + 1)


if __name__ == '__main__':
    with open('ursulet.in', 'r') as f:
        n = int(f.readline())
        altitudini = list(map(int, f.readline().split()))
    
    if not validare_altitudini(altitudini):
        print("Datele nu corespund restricțiilor impuse.")
    else:
        print("Datele sunt introduse corect.")
        oboseala_max, inceput, sfarsit = obos_max(altitudini)
        with open('ursulet.out', 'w') as f:
            f.write(str(oboseala_max) + '\n')
            f.write(str(inceput) + ' ' + str(sfarsit) + '\n')

Explicatie Rezolvare

În funcția validare_altitudini(altitudini) se verifică dacă toate valorile altitudinilor îndeplinesc condițiile impuse de problema (sunt numere întregi între -1000 și 1000). Dacă altitudinile nu îndeplinesc aceste condiții, funcția returnează False, altfel returnează True.

În funcția obos_max(altitudini) se parcurg altitudinile în ordine și se calculează obosiala maximă acumulată de Ursuleț pe o porțiune de zone consecutive. Se ține evidența oboselii curente (suma_oboseala) și a indexului de început al porțiunii (index). Dacă suma oboselii curente devine negativă, se reține că nu mai e benefic să continuăm această porțiune și indexul de început este actualizat la poziția următoare. Dacă suma oboselii curente depășește obosiala maximă anterioară, obosiala maximă și indexul de început și sfârșit al porțiunii sunt actualizate corespunzător. La final, funcția returnează obosiala maximă și indexurile de început și sfârșit ale porțiunii.

În blocul if __name__ == '__main__': se citesc datele de intrare din fișierul ursulet.in. Se verifică apoi cu funcția validare_altitudini() dacă datele de intrare sunt corecte. Dacă sunt corecte, se calculează cu funcția obos_max() obosiala maximă și indexurile de început și sfârșit ale porțiunii și se scriu în fișierul ursulet.out. Dacă datele de intrare nu sunt corecte, se afișează un mesaj corespunzător.