Connection Status:
Competition Arena > SnakeTurbo

SnakeTurbo

SRM 273 · 2005-11-21 · by supernova

SRM 273 · 2005-11-21 · by supernova · Dynamic Programming
Class Name: SnakeTurbo
Return Type: double
Method Name: finishTime
Arg Types: (int, int, vector<int>)
Problem Statement

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.

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

Submissions are judged against all 110 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SnakeTurbo with a public method double finishTime(int startLocation, int endLocation, vector<int> orbs) · 110 test cases · 2 s / 256 MB per case

Submitting as anonymous