Grid Speed

Consider a grid in which north-south streets, separated by gaps of $10$ miles each (the grid unit size), are elevated above east-west streets laid out in a similar fashion (see illustration for the case of a $6$ by $6$ grid). All streets are two-way. Entrance and exit ramps connect the streets at every intersection. Because there are no traffic lights, switching from a north-south street to an east-west street, and vice versa, takes essentially no time. The grid has very little traffic, but the local police patrol so carefully for speeding that there are virtually no speeders.

\includegraphics[width=0.9\textwidth ]{gridspeed}

The speed limits follow an unusual pattern. The speed limits are separately posted for each street and are the same for the entire street in both directions. In the illustration above, let us label the intersections using their column and row numbers: the southwestern corner of the grid is $(1,1)$, the southeastern corner is $(6,1)$, and so on. Part of your task is to determine the shortest time in which we can get from $(1,1)$ to $(6,3)$ while obeying speed limits.

However, after the Kyoto disagreement, just being fast is not good enough, one also has to be fuel efficient. Fuel consumption of a car is given in miles-per-gallon (mpg) and depends on speed of the car. Speed of a car is given in miles-per-hour (mph) and, in this digital age, the speed of a car is always a positive integer multiple of $5$. The formula relating mpg to mph is a very simple one: a car travelling at $v$ mph makes $80 - 0.03 \cdot v^2$ mpg. In a given grid of streets we would like to travel from intersection $(x_{s}, y_{s})$ to intersection $(x_{t}, y_{t})$. You are to determine the fastest and the most fuel efficient way of making the trip such that:

  • the car only changes its speed at intersections (not between intersections),

  • the car obeys all speed limits,

  • the car travels the shortest possible distance (i.e., the Manhattan distance) between the start and finish, and

  • the car arrives at the destination within a given time interval.


The input occupies $5$ lines. The first line contains an integer $2 \le n \le 10$ which is the number of horizontal and vertical streets. The second line contains a positive integer which is the grid unit size in miles, smaller than $100$. The third and fourth lines contain $n$ positive integers each, specifying the speed limits on the horizontal and vertical streets, respectively. No speed limit is smaller than $5$ or larger than $50$. The last line of data contains $6$ integers. The first four are $x_{s}$, $y_{s}$, $x_{t}$, and $y_{t}$. The last two integers give the shortest and the longest allowed time to travel in minutes, inclusive, both not larger than $1000$.


If the travel is possible then output two lines, using the format shown below. On the first line, report the earliest possible arrival time (but within the imposed limits) and fuel consumed (least possible for this travel time) and, on the second line, report the earliest arrival time (but within the imposed limits) that consumes the minimum amount of fuel. Both numbers should be given with an absolute or relative error of at most $10^{-6}$. If the travel is not possible, then output “IMPOSSIBLE”.

Sample Input 1 Sample Output 1
10 20 30 40 50 50 50 50
50 50 50 50 50 50 40 50
2 3 7 8 300 320
The earliest  arrival: 300 minutes, fuel 6.250000000 gallons
The economical travel: 317.142857143 minutes, fuel 5.599710983 gallons
Sample Input 2 Sample Output 2
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39
Sample Input 3 Sample Output 3
30 20 20 10 10 20 10 10 20 20
40 20 10 20 10 20 20 10 10 20
1 1 10 10 100 500
The earliest  arrival: 405.0 minutes, fuel 4.136029412 gallons
The economical travel: 498.0 minutes, fuel 2.760504202 gallons
CPU Time limit 5 seconds
Memory limit 1024 MB
Difficulty 6.2hard
Statistics Show
License Creative Commons License (cc by)

Please log in to submit a solution to this problem

Log in