Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Jumping Frog
Description A rivulet is situated in the heartland of Byterland. For centuries it was renowned for its beauty but the beauty is now gone. During the recent years, an increasing number of people have built their villas by the riverside and kept dumping garbage into the rivulet. This evening a little frog loses himself on the river when he is hurrying home. The figure above shows why the frog gets lost. Seen from above, garbage dumped into the river sticks together and become beam-shaped blocks that extend from the mid-axis ( The little frog is going home by jumping from one leaf to another. At first it is standing on the leftmost leaf and its home is where the rightmost leaf lies. The frog jumps straight and it cannot jump higher than the garbage blocks. If the trajectory of its jump touches any garbage, it will get stuck in and have little chance to get out. Please calculate the minimal distance the frog has to jump before arriving at home or determine that it is impossible to go home. Sizes of the frog and the leaves and thickness of the garbage blocks are negligible in your calculation. Input For l + 1. The characters in a string describe the leaves in a segment from left to right. A character is one of _{i}`A` …`Z` and `b` …`z` , indicating an ordinate of 0…25 and −1…−25 respectively.Each test case starts with This is a multiple test cases problem. Test cases are followed by blank lines. Please process to the end of the input. Output For each test case, output a single line with a real number representing the minimal distance (rounded up to 4 digits after the decimal point) the frog has to jump from the leftmost leaf to the rightmost one. Output −1 if the poor frog can never get home. Sample Input 3 b CCbB bA 3 bbb bB b 2 B b 3 O K q Sample Output 10.8507 10.6212 -1 30.2655 Hint Explanation for the sample test cases: - For the first case: This case follows the figure above.
- For the second case: Sometimes the little frog needs to jump from right to left.
- For the fourth case: The frog can jump directly from the first to the last leaf.
Source POJ Monthly--2006.12.31, Zhu, Zeyuan |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator