TopCoder problem "ToolingUp" used in TCO07 Semi 3 (Division I Level Two)



Problem Statement

    The least common multiple (lcm) of a set of positive integers is the smallest integer that is divisible by each member of the set. It is frequently desirable to have a collection of numbers whose lcm is large.

We want to manufacture parts in a greater variety of sizes -- specifically our goal is to offer sizes whose lcm is greater than or equal to targetLcm. But every new size s that we manufacture costs us s dollars to tool up to produce.

The int[] sizes contains all the sizes we are currently producing. The String targetLcm represents an integer with no leading zeroes. Return the minimum cost of offering additional sizes that will let us achieve our goal.

 

Definition

    
Class:ToolingUp
Method:cost
Parameters:String, int[]
Returns:int
Method signature:int cost(String targetLcm, int[] sizes)
(be sure your method is public)
    
 

Constraints

-targetLcm will contain only digits ('0' - '9').
-targetLcm will represent an integer between 1 and 1015, inclusive.
-targetLcm will not contain leading zeroes.
-sizes will contain between 1 and 50 elements, inclusive.
-Each element of sizes will be between 1 and 1000, inclusive.
 

Examples

0)
    
"193"
{82,13,100}
Returns: 0
Our existing sizes already have a big enough lcm.
1)
    
"1000000"
{100,92,77}
Returns: 9
We can produce a single new size of 9 to get an lcm greater than 1,000,000. (We could also achieve our goal by adding the two sizes 3 and 8, but that would cost 11.)
2)
    
"999999"
{124,600,7,8}
Returns: 11
3)
    
"123456789123"
{31,1,1,6}
Returns: 120

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10841&pm=7621

Writer:

dgoodman

Testers:

PabloGilberto , Cosmin.ro , Olexiy , ivan_metelsky

Problem categories:

Math, Search