4220 - Alimentarea Masinii

Cerința

Într-un ținut îndepărtat, un șofer trebuie să călătorească de la un capăt la altul al unui drum lung și pustiu. Pe acest drum există benzinării la diverse distanțe de la punctul de plecare. Mașina șoferului are o capacitate limitată a rezervorului, iar șoferul dorește să ajungă la destinație cu un număr minim de opriri la benzinării pentru a alimenta.

Date de intrare

Programul citește de la tastatură:

Un număr întreg distanta_totala reprezentând distanța totală până la destinație. Un număr întreg capacitate_rezervor reprezentând capacitatea rezervorului mașinii. Un număr întreg numar_benzinarii reprezentând numărul de benzinării de pe drum. O listă de numar_benzinarii numere întregi reprezentând distanțele la care se află benzinăriile de la punctul de plecare.

Date de ieșire

Pe ecran se va afișa numărul minim de opriri necesare pentru a ajunge la destinație. Dacă nu este posibil să ajungi la destinație, se va afișa "-1".

Exemplu 1

Intrare

distanta_totala = 1000 capacitate_rezervor = 400 numar_benzinarii = 4 benzinarii = [200, 375, 550, 750]

Iesire

2

Exemplu 2

Intrare

distanta_totala = 500 capacitate_rezervor = 200 numar_benzinarii = 3 benzinarii = [100, 200, 300]

Iesire

-1

Rezolvare

def numar_minim_opriri(distanta_totala, capacitate_rezervor, numar_benzinarii, benzinarii):
    benzinarii.append(distanta_totala)
    benzinarii.sort()

    opriri = 0
    pozitie_curenta = 0
    carburant_ramas = capacitate_rezervor
    i = 0

    while pozitie_curenta < distanta_totala:
        distanta_maxima = pozitie_curenta + carburant_ramas
     
        while i < len(benzinarii) and benzinarii[i] <= distanta_maxima:
            i += 1


        if pozitie_curenta == benzinarii[i - 1]:
            return -1

  
        if pozitie_curenta < distanta_totala:
            pozitie_curenta = benzinarii[i - 1]
            carburant_ramas = capacitate_rezervor
            if pozitie_curenta < distanta_totala:
                opriri += 1

    return opriri


def main():
    distanta_totala = int(input("Introduceți distanța totală până la destinație: "))
    capacitate_rezervor = int(input("Introduceți capacitatea rezervorului: "))
    numar_benzinarii = int(input("Introduceți numărul de benzinării: "))

    if numar_benzinarii > 0:
        benzinarii = list(
            map(int, input("Introduceți distanțele la care se află benzinăriile, separate prin spațiu: ").split()))
    else:
        benzinarii = []

    rezultat = numar_minim_opriri(distanta_totala, capacitate_rezervor, numar_benzinarii, benzinarii)

    if rezultat == -1:
        print("Nu este posibil să ajungi la destinație.")
    else:
        print(rezultat)


if __name__ == "__main__":
    main()