1804 - ursulet

Sursa: 1804 - ursulet

---

Cerinţa

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

Dacă datele sunt introduse corect, pe ecran se va afișa: "Datele sunt introduse corect." fișierul de ieșire ursulet.out va conține 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

<syntaxhighlight lang="python" line>

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

</syntaxhighlight>

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.