Fence Repair#1529
You need to repair an old fence consisting of a series of planks, some of which are broken. The planks are numbered from left to right in increasing order.
Repairing all planks from the -th to the -th inclusive (where i \leq j) costs \sqrt{j - i + 1}. To reduce the total repair cost, it is sometimes advantageous to repair even intact planks. Your task is to find the minimum cost to repair the entire fence.
You are given information about the fence. Broken planks are denoted by the symbol X, and intact ones by the symbol .. Find the minimum cost to repair the entire fence.
Each line represents a separate test describing the state of the fence. It consists only of the following symbols:
X — broken plank;
. — intact plank;
The length of the line (fence) does not exceed characters.
For each test, print in a separate line the minimum cost to repair the entire fence with decimal places.
Example 1