Dennis Shasha

Omniheurist Course

Computer Science



You are in charge of designing the denominations of coins. In the U.S., the denominations are penny, nickel, dime, quarter, half dollar, and dollar. Ignore the dollar coin for now. You have made a study of the subdollar prices and have determined that each multiple of 5 cents price is N times as likely as a non-multiple of 5 cents. For example, if N = 4, then 15 cents is four times as likely to be the price as 43 cents. But any 5 cent multiple is equally likely as any other 5 cent multiple and ditto for the non-5 cent 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 total score would be (99-19)*2 + (19*N*2). Please print out the score and the denominations.