3687 - Back to the Himalayas

Cerinta

Cum găsește căprioara apa rece de izvor, tot așa găsesc eu banii și în vârful munților! – Jany MooRANDy

A trecut așa mult timp de când bombardierul vostru favorit Jany MooRANDy a vizitat Himalaya și dușmanii lui au început să-i conteste abilitățile sale de a face bani. Nu vă faceți probleme, el a ajuns înapoi în Himalaya să demonstreze înca o dată de ce este în stare: “Să bată vântul și ploaia, eu fac bani și-n Himalaya! Unde fac eu bani pachete, dușmanii culeg doar pietre!”. După ce a obținut doctoratul în fizică demonstrând astfel multiplele sale abilități, el a schimbat “legea conservării energiei” în “legea conservării valorii”.Legea spune așa: Valoarea cinetică a unui obiect e egală cu m * v * v / 2, unde m e masa obiectului și v e viteza lui, iar valoarea potențială a obiectului este m * g * h, unde m e masa obiectului, g e accelerația gravitațională, pe care o presupunem ca fiind 10, iar h e diferența de înălțime dintre ea și un punct de referință.Așa cum știm cu toții, Himalaya are n vârfuri muntoase, situate într-o linie, al i-lea vârf având înălțimea h[i]. Acum Jany MooRANDy vrea să încaseze banii câștigați de stațiile de telecabină din fiecare din cele n vârfuri muntoase. Începând de la un vârf i el se poate deplasa doar spre dreapta, spre vârful n. Deoarece el are multă valoare, el începe călătoria cu o valoare cinetică de m * v * v / 2. Când sare din vârful i către vârful i+1, el fie câștigă, fie pierde valoare. Dacă h[i] ≥ h[i+1], el va câștiga m * g * (h[i] - h[i+1]) valoare, iar dacă h[i] < h[i+1], el va pierde m * g * (h[i+1] - h[i]) valoare. De-a lungul călătoriei, valoarea lui nu poate scădea sub 0. Pentru ca el vrea să faca bani pachete, vrea să știe pentru fiecare punct de start care este cel mai depărtat punct spre care el se poate deplasa?

Date de intrare

Programul citește de la tastatură pe prima linie numerele n, m și v, numărul de vârfuri, masa și viteza lui Jany MooRANDy. Pe următoarea linie, se vor citi n numere, reprezentând înălțimile celor n vârfuri.

Date de ieșire

Programul va afișa pe ecran n numere, reprezentând răspunsul cerut pentru fiecare vârf.

Restricții și precizări

• 1 ≤ n ≤ 500 000

• 1 ≤ m ≤ 1050

• 1 ≤ v ≤ 40 000

• cele n numere citite vor fi mai mici decât 1.000.000.000

• Problema nu necesită cunoștinte de fizică pentru a fi rezolvată.

• Pentru teste în valoare de 30 de puncte, 1 ≤ n ≤ 1000, 1 ≤ v ≤ 400, 1 ≤ m ≤ 109

• Pentru alte teste în valoare de 30 de puncte, 1 ≤ n ≤ 1000

Exemplul 1

intrare

9 2 7

3 2 1 5 3 3 8 2 1

iesire

Datele introduse corespund restrictiilor impuse.

6 3 3 6 6 6 9 9 9

Exemplul 2

intrare

-10 44 24

14 12 45 654 87 65 43 22 99

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

<syntaxhighlight lang="python3" line="1">

def maximizare_valoare(n, h):

   m = 1  # masa obiectului
   g = 10  # accelerația gravitațională

   # Inițializăm lista valorilor maxime cu zero-uri
   maxime_valori = [0] * n

   # Parcurgem vârfurile în ordine inversă
   for i in range(n - 2, -1, -1):
       # Calculăm valoarea maximă pentru vârful curent
       maxima_valoare = max(maxime_valori[i + 1] + m * g * max(0, h[i] - h[i + 1]), 0)
       maxime_valori[i] = maxima_valoare

   return maxime_valori

</syntaxhighlight>