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
300
4
200 475 550 750

Iesire

3

Rezolvare

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