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

Ieșire

6 3 3 6 6 6 9 9 9

Explicație

Hai să vedem de ce ans[1] = 6.

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

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

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

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

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

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

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

Astfel, Jany poate ajunge de la vârful 1 la vârful 6.

Exemplul 2:

Intrare

9 2 40001
3 2 1 5 3 3 8 2 1

Ieșire

Datele nu corespund restrictiilor impuse

Rezolvare

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