PROBLEM STATEMENT
You are going to repair an old fence. The fence consists of several consecutive boards, some of
which are broken and some of which are fine. The boards are numbered from left to right in
increasing order. To repair all the boards between i and j, inclusive, where j is greater than or
equal to i, a woodworker charges sqrt(j-i+1), where sqrt is the square root function. Due to the
woodworker's pricing scheme, it is often necessary to repair boards even if they are not broken in
order to get the best price (see examples).
You will be given a vector boards. Concatenate the elements of boards to create a single
string representing the fence from left to right. Broken boards are represented by 'X' characters
and good boards are represented by '.' characters. Return the minimal cost required to repair all
broken boards.
DEFINITION
Class:FenceRepairing
Method:calculateCost
Parameters:vector
Returns:double
Method signature:double calculateCost(vector boards)
NOTES
-Your return value must have an absolute or relative error less than 1e-9.
CONSTRAINTS
-boards will contain between 1 and 50 elements, inclusive.
-Each element of boards will contain between 1 and 50 characters, inclusive.
-Each element of boards will contain only '.' and uppercase 'X' characters.
EXAMPLES
0)
{"X.X...X.X"}
Returns: 3.0
The best choice is to repair the entire fence at once. This will cost sqrt(8-0+1) = 3.
1)
{"X.X.....X"}
Returns: 2.732050807568877
The best choice is to perform two repairs. First, repair the three leftmost boards. Then, repair
the rightmost board. The total cost is sqrt(2-0+1) + sqrt(8-8+1) = 2.73.
2)
{"X.......", "......XX", ".X......", ".X...X.."}
Returns: 5.0
3)
{".X.......X", "..........", "...X......", "...X..X...", "..........",
"..........", "..X....XX.", ".........X", "XXX", ".XXX.....X"}
Returns: 9.591663046625438
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.