TopCoder problem "ChangeOMatic" used in SRM 420 (Division I Level Three)



Problem Statement

    

The Change-O-Matic is a deterministic machine with a single goal: to provide change. That is, you throw in a banknote or a coin, and the machine throws out a bunch of smaller coins with the same total value.

More precisely, the Change-O-Matic operates as follows:

The machine contains several large stacks of coins. The values of these coins are given as a int[] outputValues. For the purpose of this problem we may assume that the machine contains an infinite number of coins of each of these values. One of the available values is always 1.

The customer may throw in any coin or banknote with value greater than 1. The machine will output a set of at least two coins with the same total value. If there are multiple ways to satisfy this requirement, the machine prefers the one where the total number of output coins is minimized. If there are still multiple ways, the machine prefers the one that is lexicographically maximal (see Notes for a precise definition).

You have a single banknote, and its value is given as a long inputValue. You would like to change it into coins of value 1 each. Return the number of times you have to throw something into the machine.

 

Definition

    
Class:ChangeOMatic
Method:howManyRounds
Parameters:int[], long
Returns:long
Method signature:long howManyRounds(int[] outputValues, long inputValue)
(be sure your method is public)
    
 

Notes

-Let A=(a1,...,aN) and B=(b1,...,bN) be two different but equally large sets of coins, with a1 >= a2 >= ... >= aN and b1 >= b2 >= ... >= bN. Let x be the smallest index such that ax != bx. If ax > bx, we say that the set A is lexicographically larger than the set B.
-Given a collection of different but equally large sets of coins, the lexicographically maximal set is the one that is lexicographically larger than each of the other sets. (Note that there is always exactly one such set.)
 

Constraints

-outputValues will contain between 1 and 50 elements, inclusive.
-outputValues will be sorted in strictly ascending order. That is, for each i, outputValues[i] < outputValues[i+1].
-Each element of outputValues will be between 1 and 1,000, inclusive.
-Element 0 of outputValues will be equal to 1.
-inputValue will be between 2 and 10^15, inclusive.
 

Examples

0)
    
{1,5,10}
21
Returns: 7
The process of changing your money may look as follows: 
You insert:    You get:      You then have:
21             10+10+1       10+10+1
10             5+5           10+5+5+1
5              1+1+1+1+1     10+5+1+1+1+1+1+1
10             5+5           5+5+5+1+1+1+1+1+1
5              1+1+1+1+1     5+5+(eleven times 1)
5              1+1+1+1+1     5+(sixteen times 1)
5              1+1+1+1+1     twenty-one coins worth 1 each
1)
    
{1,33,90,91,92,93,94,95,96,97,98}
99
Returns: 12
In each step, the machine minimizes the number of coins it throws out, not the number of steps you need to accomplish your task. In the first step it will output a coin worth 98 and a coin worth 1.
2)
    
{1,30,60}
50
Returns: 2
The value of the banknote may be less than the values of some coin types.
3)
    
{1,30,60,90}
60
Returns: 3
The value of the banknote may even be equal to the value of some coin type. Note that for any input the machine must always output at least two coins. Therefore if you throw in the banknote worth 60, you will get two coins worth 30 each.
4)
    
{1,8,9,11,12,100}
120
Returns: 37
In the first step the machine would output 100+12+8. (The combination 100+11+9 has the same number of coins, but 100+12+8 is lexicographically larger.)

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=9963

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13511&pm=9963

Writer:

misof

Testers:

PabloGilberto , Olexiy , ivan_metelsky , zhuzeyuan

Problem categories:

Dynamic Programming, Greedy, Simple Math