A young couple needs to build a fence around their yard to keep the deer from eating their azaleas. The fence will start at one corner of their house and end at another. The perimeter of their yard is marked by trees, and the fence must follow that perimeter. Furthermore, the fencing is sold in lengths of L and, to avoid setting fenceposts, each segment of fencing must start and end at either a corner of the house or a tree; the next segment then starts at the tree where the previous segment ended. Segments less than L are possible, but the scraps may not be reused in other parts of the fence.

Devise a (n) algorithm to determine the minimum number of fencing segments the new couple must buy to complete their fence, and prove that your algorithm is correct. The inputs should be as follows:

• d, a non-empty list of the distances along the perimeter of the yard to each tree in increasing order, starting with 0.0 for the first corner of the house, with no two consecutive elements more than L apart, and ending with the total length of the perimeter;
• L, the length of the segments of fencing; and
• n, the number of trees along the perimeter (so the number of elements in d is n+2).

The output should be the ordered list of k+1 segment endpoints, where k is the number of segments used. You may use a simple sequential search as part of your algorithm without proving that the sequential search is correct (although that is a good exercise).