TopCoder problem "SnakeTurbo" used in SRM 273 (Division I Level Two)



Problem Statement

    Already a master of the classical Snake games, you are looking for a new challenge. This time, you are controlling a snake that can move left or right, on a single axis. Your goal is to move it from startLocation to endLocation in a minimum amount of time. When you start the game, the snake has a speed of one unit of space per one unit of time. But whenever it encounters a magic orb, its speed doubles.



You are given a int[] orbs, where each element denotes the location of an orb. The orbs are always placed at integer coordinates, and can be treated as points. An orb can only be used once; it loses its magical powers after being used. You can assume the snake movement is continuous, which means that it cannot skip any intermediate points on the axis. Determine the minimum time needed to reach endLocation.
 

Definition

    
Class:SnakeTurbo
Method:finishTime
Parameters:int, int, int[]
Returns:double
Method signature:double finishTime(int startLocation, int endLocation, int[] orbs)
(be sure your method is public)
    
 

Notes

-Your return value must have an absolute or relative error less than 1e-9.
 

Constraints

-orbs will contain between 0 and 50 elements, inclusive.
- startLocation and endLocation will each be between 0 and 1000000000, inclusive.
-Each element in orbs will be between 0 and 1000000000, inclusive.
-All elements in orbs will be distinct, and also different from startLocation and endLocation .
 

Examples

0)
    
10
20
{2, 18, 8}
Returns: 7.5
The best solution is to move left to the orb at location 8 and then turn right, use the orb at location 18, and finish at location 20. The time needed is: 
 |10 - 8| * 1 + |8 - 18| * 0.5 + |20 - 18| * 0.25 = 2 + 5 + 0.5 = 7.5.
Note that '|' denotes absolute value.



Moving directly from location 10 to location 20 has a time cost of 9, while moving from location 10 to location 2 and then to location 20 has a time cost of 9.25.
1)
    
10
0
{1, 2, 3, 4, 5, 6, 7, 8, 9}
Returns: 1.998046875
2)
    
77
77
{27, 127}
Returns: 0.0
3)
    
0
100000000
{99999999}
Returns: 9.99999995E7
4)
    
100
200
{99, 102, 96, 108, 84, 132, 36}
Returns: 8.375

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=5893

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8070&pm=5893

Writer:

supernova

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming