首页 > ACM题库 > HDU-杭电 > hdu 2928 A Rod in a Path待解决
2014
02-23

hdu 2928 A Rod in a Path待解决

A Rod in a Path

问题描述 :

Alice has a rod. One day, she draws a path on a grid and puts the rod on it. The path begins at (0, 0) and continues to the right. The first and last segments are always horizontal, so there are always an odd number of segments. If we number the segments 1, 2, … , n, odd-numbered segments are all horizontal, while other segments (if any) are vertical. Initially, one endpoint B of the rod is located at (0, 0), and the other endpoint A is at (L, 0), where L is the length of the rod. The length of the first segment is at least L. When moving the rod, both endpoints A and B must be always on the path, though other parts may be outside. The rod is hard, so its length (i.e. distance between A and B) is always L.

Write a program to compute the minimum distance A must cover to reach the rightmost endpoint of the path.

输入:

The input consists of several test cases. The first line of each case contains two integers n and L (1 ≤ n ≤ 10, 1 ≤ L ≤ 30),described above. The second line contains n non-zero integers li (-30 ≤ li ≤ 30), the lengths and directions of path segments. The absolute value of li denotes length of the i-th segment. If it is horizontal, li is positive. That means, horizontal segments are always left-to-right. If it is vertical, positive means down-to-up (increasing y coordinate), negative means up-to-down (decreasing y coordinate). The last test case is followed by a single zero, which should not be processed.

输出:

The input consists of several test cases. The first line of each case contains two integers n and L (1 ≤ n ≤ 10, 1 ≤ L ≤ 30),described above. The second line contains n non-zero integers li (-30 ≤ li ≤ 30), the lengths and directions of path segments. The absolute value of li denotes length of the i-th segment. If it is horizontal, li is positive. That means, horizontal segments are always left-to-right. If it is vertical, positive means down-to-up (increasing y coordinate), negative means up-to-down (decreasing y coordinate). The last test case is followed by a single zero, which should not be processed.

样例输入:

3 5
8 6 2
5 2
3 1 1 -4 1
0

样例输出:

Case 1: 11.00
Case 2: 10.00


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. 因为是要把从字符串s的start位到当前位在hash中重置,修改提交后能accept,但是不修改居然也能accept