Description

In her darkened tent, at the edge of the carnival, against the haunting sound of a distant calliope, she gazes into her crystal ball, and to you she says:

“You are going on a long journey. You will start on the road at mile post 0. Along the way there are ?? castles, located at mile posts ??1 < ??2 < ⋯ < ????, where each ???? is measured from the starting point. The only places you are allowed to stop are at these castles, but you can choose which of the castles at which you stop. However, you are required to stop at the final castle (at a distance of ????) because that, my young programmer, is your destination, your destiny, your fate.

Ideally, you should travel exactly ?? miles a day, but this may not be possible because of the spacing of the castles. If you travel ?? miles during a day, there is a penalty for departing from the ideal distance, given by the formula (?? − ??)2. You want to plan your trip so as to minimize the total penalty, i.e., the sum, over all travel days, of the daily penalties.”

In this assignment, you will do as Madame Sosostris wishes and plan the journal to the final, fateful castle at ????, minimizing the penalty

Input: The input of the program will be a file consisting of two lines. The first line consists of the value ??, the ideal number of miles traveled in a day. The second line consists of integers separated by tab characters, giving the location of the castles from the starting point

Output: The output will be (1) a sequence of integers giving the locations of the castles at which you stop to give a minimum penalty as well as, on a second line, (2) what that total penalty will be. Sample test files are posted with this assignment

Analysis: With the program should be submitted a document describing the algorithm you have devised. This part of the assignment is intended to simulate the real-world writing experience in which you as assigned the task of designing algorithm and the document you produce will be read by managers and implementers. The prose should be clear, objective and professional. After reading your document, managers should understand the main idea and implementers should be able to proceed without the necessity of additional creative thought. Where appropriate equations that show the main insight should be provided, especially the recurrence that defines the problem in the case of dynamic programming solutions. Etiological matters should be avoided unless they are vehicles for offering algorithmic insight. (An example might be that you identified the problem as a variant of another we have studied). The anticipated length is a page or so.