Ava has decided to go on a hiking trip on the Massanutten Trail (a 71 mile trail in central Virginia). She will carry a half gallon of water in her canteen, will start with a full canteen, and can hike m miles before running out of water if the canteen is full. Her Virginia state map shows where she can get more water along the trail and she has used this to compute the distances between each locations. If Ava wants to minimize the number of stops for water, what would be an efficient strategy?

(a) Show that this problem has an optimal substructure:

(b) Show that this problem greedy-choice property:

(c) Give your solution and the runtime of your solution: