Vizualizare sursă pentru „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 <code>m * v * v / 2</code>, unde <code>m</code> e masa obiectului și <code>v</code> e viteza lui, iar valoarea potențială a obiectului este <code>m * g * h</code>, unde <code>m</code> e masa obiectului, <code>g</code> e accelerația gravitațională, pe care o presupunem ca fiind <code>10</code>, iar <code>h</code> e diferența de înălțime dintre ea și un punct de referință.

Așa cum știm cu toții, Himalaya are <code>n</code> vârfuri muntoase, situate într-o linie, al i-lea vârf având înălțimea <code>h[i]</code>. Acum Jany MooRANDy vrea să încaseze banii câștigați de stațiile de telecabină din fiecare din cele <code>n</code> vârfuri muntoase. Începând de la un vârf <code>i</code> el se poate deplasa doar spre dreapta, spre vârful <code>n</code>.

Deoarece el are multă valoare, el începe călătoria cu o valoare cinetică de <code>m * v * v / 2</code>. Când sare din vârful <code>i</code> către vârful <code>i+1</code>, el fie câștigă, fie pierde valoare. Dacă <code>h[i] ≥ h[i+1]</code>, el va câștiga <code>m * g * (h[i] - h[i+1])</code> valoare, iar dacă <code>h[i] < h[i+1]</code>, el va pierde <code>m * g * (h[i+1] - h[i])</code> valoare. De-a lungul călătoriei, valoarea lui nu poate scădea sub <code>0</code>. 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 <code>n</code>, <code>m</code> și <code>v</code>, numărul de vârfuri, masa și viteza lui Jany MooRANDy.

Pe următoarea linie, se vor citi <code>n</code> numere, reprezentând înălțimile celor <code>n</code> vârfuri.

= Date de ieșire =
Programul va afișa pe ecran <code>n</code> numere, reprezentând răspunsul cerut pentru fiecare vârf.

= Restricții și precizări =

* <code>1 ≤ n ≤ 500 000</code>
* <code>1 ≤ m ≤</code>  <code>1050</code>
* <code>1 ≤ v ≤ 40 000</code>
* cele <code>n</code> numere citite vor fi mai mici decât <code>1.000.000.000</code>
* Problema nu necesită cunoștinte de fizică pentru a fi rezolvată.
* Pentru teste în valoare de <code>30</code> de puncte, <code>1 ≤ n ≤ 1000</code>, <code>1 ≤ v ≤ 400</code>, <code>1 ≤ m ≤</code>  <code>109</code>
* Pentru alte teste în valoare de <code>30</code> de puncte, <code>1 ≤ n ≤ 1000</code>

= Exemplul 1: =
Intrare
 9 2 7
 3 2 1 5 3 3 8 2 1
Ieșire
 6 3 3 6 6 6 9 9 9

=== Explicație ===
Hai să vedem de ce <code>ans[1] = 6</code>.

El pornește din primul vârf cu valoare cinetică de <code>49</code>.

De la vârful <code>1</code> la vârful <code>2</code>, valoarea lui crește cu <code>20</code>, deci devine <code>69</code>.

De la vârful <code>2</code> la vârful <code>3</code>, valoarea lui crește cu <code>20</code>, deci devine <code>89</code>.

De la vârful <code>3</code> la vârful <code>4</code>, valoarea lui scade cu <code>80</code>, deci devine <code>9</code>.

De la vârful <code>4</code> la vârful <code>5</code>, valoarea lui crește cu <code>40</code>, deci devine <code>49</code>.

De la vârful <code>5</code> la vârful <code>6</code>, valoarea lui rămâne la <code>49</code>.

De la vârful <code>6</code> la vârful <code>7</code>, valoarea lui scade cu <code>100</code>, deci devine <code>-51</code>, așa că nu mai poate continua drumul.

Astfel, Jany poate ajunge de la vârful <code>1</code> la vârful <code>6</code>.

== Exemplul 2: ==
Intrare
 9 2 40001
 3 2 1 5 3 3 8 2 1
Ieșire
 Datele nu corespund restrictiilor impuse

== Rezolvare == 
<syntaxhighlight lang="python3" line="1">
import sys

# Definirea limitelor și variabilelor
N_MAX = 500000
H = [0] * (N_MAX + 5)
S = [0] * (N_MAX + 5)
ans = [0] * (N_MAX + 5)
L = 0

def get_ans(idx, N, v):
    ret = N + 1
    le, ri = 1, L
    while le <= ri:
        mid = (le + ri) // 2
        if 20 * H[S[mid]] > 20 * H[idx] + v * v:
            ret = S[mid]
            le = mid + 1
        else:
            ri = mid - 1
    return ret - 1

def main():
    global L
    # Citirea datelor de intrare
    try:
        N, dummy, v = input().split()
        N, v = int(N), int(v)
    except ValueError:
        print("Datele introduse nu respectă restricțiile")
        return

    # Verificare restricții pentru N și v
    if not (1 <= N <= 500000 and 1 <= v <= 40000):
        print("Datele introduse nu respectă restricțiile")
        return

    # Citirea înălțimilor de pe o singură linie
    try:
        H[1:N+1] = map(int, input().split())
    except ValueError:
        print("Datele introduse nu respectă restricțiile")
        return

    # Verificarea restricțiilor pentru înălțimi
    if any(h >= 1000000000 for h in H[1:N+1]):
        print("Datele introduse nu respectă restricțiile")
        return

    # Logica principală a programului
    for i in range(N, 0, -1):
        while L > 0 and H[S[L]] <= H[i]:
            L -= 1
        L += 1
        S[L] = i
        ans[i] = get_ans(i, N, v)

    # Afișarea răspunsurilor
    for i in range(1, N + 1):
        print(ans[i], end=" ")
    print()

if __name__ == "__main__":
    main()

</syntaxhighlight>