FenceRepairing
SRM 325 · 2006-11-02 · by Andrew_Lazarev
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
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.
{"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.
{"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.
{"X.......", "......XX", ".X......", ".X...X.."}
Returns: 5.0
{"..X.......","X.........","..........","......X..X"}
Returns: 4.0
{".....",".X.X.","....."}
Returns: 1.7320508075688772
Submissions are judged against all 59 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class FenceRepairing with a public method double calculateCost(vector<string> boards) · 59 test cases · 2 s / 256 MB per case