PROBLEM STATEMENT
After a recent construction project, you have found that you have some wooden planks of various
lengths left over. Knowing that wood is quite valuable, you are going to try to sell them. A local
hardware store has offered to buy the planks, but in order to make a retail display they want all
the planks they buy to be the same length and they want this length to be some integer value. A
local workshop can cut the planks into different lengths for you, but they charge costPerCut for
every cut they make. The hardware store will pay woodValue per unit length for the planks that
they buy (i.e., if you bring them K planks, each L units long, then they'll pay you K * L *
woodValue). Any leftover wood will be thrown away. What is the maximum amount of money that you
can make?
You are given a vector lengths, in which each element is the length of a single plank of
wood. Return an int containing the maximum amount of money that you can make.
DEFINITION
Class:Planks
Method:makeSimilar
Parameters:vector , int, int
Returns:int
Method signature:int makeSimilar(vector lengths, int costPerCut, int woodValue)
CONSTRAINTS
-lengths will contain between 1 and 50 elements, inclusive.
-Each element of lengths will be between 1 and 10000, inclusive.
-woodValue and costPerCut will each be between 1 and 1000, inclusive.
EXAMPLES
0)
{26,103,59}
1
10
Returns: 1770
Here, wood is very valuable, while making cuts is very cheap. We can therefore make a large number
of cuts to reduce the amount of wood wasted as much as possible. It is optimal to cut the planks
into smaller planks of length 6. Cut the first plank into 4 pieces of length 6 and 1 of length 2,
the second into 17 pieces of length 6 and 1 of length 1 and the the third into 9 pieces of length
6 and 1 of length 5. In total we have 30 pieces of length 6 that we can sell and have made 30
cuts. The total amount of money we make is therefore:
30 * 6 * 10 - 30 * 1
= 1770
1)
{26,103,59}
10
10
Returns: 1680
These are the same three planks, but now making a cut is far more expensive. It is now optimal to
cut the planks to a common length of 25.
2)
{26,103,59}
100
10
Returns: 1230
Now making a cut is really expensive. Here it is optimal to throw the smallest plank away
entirely. Cut the remaining two into 51 unit lengths.
3)
{5281,5297,5303,5309,5323,5333,5347,5351,5381,5387}
5
20
Returns: 1057260
4)
{31,73,127,179,181,191,283,353,359,1019}
25
10
Returns: 25145
5)
{200,200,200,400}
1000
1
Returns: 600
Throw away the plank of length 400 and just sell the three planks of length 200.
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.