You are in charge of designing the denominations of coins. However, we're going to do this for old English pounds which were worth 240 pence. You have made a study of the subpound prices and have determined that each multiple of 5 cents price is N times as likely as a non-multiple of 5 pence. For example, if N = 4, then 15 pence is four times as likely to be the price as 43 pence. But any 5 pence multiple is equally likely as any other 5 pence multiple and ditto for the non-5 pence multiples. The N will be given in class and your programs will have 2 minutes to solve each of the following two problems. (N will be 1 or greater but may not be an integer.)
Hint: dynamic programming is a good start. You can use either one dimensional dynamic programming or two dimensional dynamic programming in the spirit of string matching. That is the inner loop. As for the outer loop, you might have to think whether any coin sizes are impossible. You might also find it useful to evaluate the cost on multiples of 5s separately from the costs on non-multiples of 5.
Scoring: Score is sum of the costs of all non-multiples of 5 + sum of N * costs of the multiples of 5. For example, if the cost of every entry were 2, then the number of multiples of 5 pence would be 235/5 = 47. Then the total score would be (239-47)*2 + (47*N*2). Please print out the score and the denominations.