当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。
3166：Jumping Frog
题目描述
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 (x-axis in the figure) of the rivulet till they reach one of the banks. The garbage blocks alternate in touching the two banks and the leftmost block always touches the bank shown at the bottom. The blocks are always located at integral coordinates and they divide the rivulet into several segments of possibly different lengths. As in the figure above, there are three segments of lengths 2, 5 and 3 in order. At each integral abscissa strictly inside a segment (not on the border), there is a lotus leaf located at some ordinate. The ordinates are also integral.
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.
输入解释
For n segments divided into by n − 1 garbage blocks, you will be given n strings with the information of the coordinates of each lotus leaf. The i-th string is for the i-th segment from the left and if it is li characters long, that means the corresponding segment has length li + 1. The characters in a string describe the leaves in a segment from left to right. A character is one of A…Z and b…z, indicating an ordinate of 0…25 and −1…−25 respectively.
Each test case starts with n (1 ≤ n ≤ 50) on the first line. The next n lines each contain a non-empty string with no more than 50 characters.
This is a multiple test cases problem. Test cases are followed by blank lines. Please process to the end of the input.
输出解释
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.
输入样例
3 b CCbB bA 3 bbb bB b 2 B b 3 O K q
输出样例
10.8507 10.6212 -1 30.2655
提示
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.
最后修改于 2020-10-29T06:54:40+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
| 时间上限 | 内存上限 |
| 1000 | 131072 |