1804 - ursulet

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: ursulet.out; Datele sunt introduse correct.; 4; 2 4

Exemplu 2

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

Rezolvare

Rezolvare ver. 1

1804 - ursulet

def read_input():

   n = int(input())
   altitudes = list(map(int, input().split()))
   return altitudes

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

   max_sum, start_index, end_index = result
   with open('ursulet.out', 'w') as f:
       f.write(str(max_sum) + '\n')
       f.write(str(start_index + 1) + ' ' + str(end_index + 1) + '\n')

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__':

   altitudes = read_input()
   result = find_maximum_subarray(altitudes)
   write_output(result)

   if validate_output('ursulet.ok', 'ursulet.out'):
       print("Datele sunt introduse corect.")
   else:
       print("Datele nu corespund restricțiilor impuse.")

</syntaxhighlight>

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.

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