Editing 4220 - Alimentarea Masinii

== Cerința ==
Vrei să călătorești n kilometri din orașul A în orașul B cu o mașină care are un rezervor de combustibil care poate asigura un număr de m kilometri. Între cele două orașe sunt amplasate stații de alimentare cu combustibil. Mașina pleacă din orașul A cu rezervorul plin. Vrei să știi numărul minim de alimentări necesare parcurgerii distanței între cele două orașe sau dacă nu se poate parcurge distanța din cauza alimentării (ai o mașină electrică și nu prea sunt stații electrice de alimentare).
== Date de intrare ==
Fișierul de intrare masina.in conține pe prima linie numărul n care reprezintă distanța dintre orașele A și B, pe a doua linie numărul m care reprezintă numărul de kilometri care pot fi parcurși cu o alimentare. Pe a treia linie o valoare k reprezentând numărul de stații de alimentare. Pe a patra linie se află un șir de k valori: d[1], d[2], d[3], …, d[k] reprezentând distanța dintre fiecare stație de alimentare și orașul de pornire A.
== Date de ieșire ==
Fișierul de ieșire masina.out va conține pe prima linie numărul a, reprezentând numărul minim de alimentări dintre cele două orașe sau -1 dacă nu se poate parcurge distanța .
== Restricții și precizări ==
*1 ≤ n ≤ 205.000
*1 ≤ m ≤ 400
*1 ≤ k ≤ 1000
*1 ≤ d[i] ≤ n
== Exemplu 1 ==
;Intrare
800<br>
300<br>
4<br>
200 475 550 750

;Iesire
3

== Rezolvare ==
<syntaxhighlight lang="python" line>
def citire_date():
    with open("masina.in", "r") as f:
        n = int(f.readline().strip())
        m = int(f.readline().strip())
        k = int(f.readline().strip())
        statii = list(map(int, f.readline().strip().split()))
    return n, m, k, statii

def minim_opriri(n, m, k, statii):
    statii.append(n)  # Adaugam destinatia ca ultima statie
    statii.sort()

    opriri = 0
    pozitie_curenta = 0
    ultima_oprire = 0

    for i in range(len(statii)):
        if statii[i] - pozitie_curenta > m:
            if pozitie_curenta == ultima_oprire:
                return -1
            opriri += 1
            pozitie_curenta = ultima_oprire
        if statii[i] - pozitie_curenta <= m:
            ultima_oprire = statii[i]
    
    return opriri if pozitie_curenta != n else -1

def scrie_rezultate(rezultat):
    with open("masina.out", "w") as f:
        f.write(f"{rezultat}\n")

def main():
    n, m, k, statii = citire_date()

    # Verificarea restrictiilor
    assert 1 <= n <= 205000, "n trebuie sa fie intre 1 si 205.000"
    assert 1 <= m <= 400, "m trebuie sa fie intre 1 si 400"
    assert 1 <= k <= 1000, "k trebuie sa fie intre 1 si 1000"
    assert all(1 <= d <= n for d in statii), "fiecare d[i] trebuie sa fie intre 1 si n"

    rezultat = minim_opriri(n, m, k, statii)
    scrie_rezultate(rezultat)

if __name__ == "__main__":
    main()

</syntaxhighlight>