Je rijdt op een zeer lange snelweg, met benzinestations bij kilometerpalen m₀, m₁,…,m_n, waarbij m₀=0 je startpunt is en m_n je uiteindelijke bestemming. Je wilt zo weinig mogelijk keren stoppen om te tanken, maar met een volle tank kan je slechts M kilometer rijden. Gevraagd is om het minimum aantal tankbeurten te bepalen dat je nodig hebt, evenals de stopplaatsen waar je bijtankt.

Opgave

Schrijf een Python functie vindStopplaatsen die het aantal kilometer M voor je benzinetank en een lijst van benzinestations als parameter krijgt. De functie geeft het gevonden aantal tankbeurten terug, en een lijst van benzinestations waar je moet tanken.

Voorbeeld

>>> vindStopplaatsen(300, [0, 100, 200, 250, 330, 430, 500, 550, 600, 750, 900])
(3, [250, 550, 750])