Problème — Le moins d'arrêts à la pompe

Problème — Le moins d'arrêts à la pompe.

Une voiture doit parcourir $1000$ km sur une autoroute. Le plein lui permet de rouler $400$ km. Elle part le réservoir plein ; les stations-service se trouvent aux kilomètres [100, 250, 380, 520, 700, 850]. On veut arriver en faisant le moins d'arrêts possible (à chaque arrêt, on refait le plein).

• Stratégie gloutonne : rouler le plus loin possible, c'est-à-dire ne s'arrêter qu'à la dernière station atteignable avec le carburant restant. L'appliquer à la main.
• Écrire une fonction arrets(stations, distance, autonomie) qui renvoie la liste des stations où l'on s'arrête, ou None si le trajet est impossible.
• Que renvoie-t-elle si la station du kilomètre $380$ est fermée ? Si les stations $380$ et $520$ sont fermées ?
• Justifier que la stratégie est optimale.