编程介的小学生 2017-09-15 16:06 采纳率: 20.5%
浏览 860
已采纳

Grid Speed

Description

Consider a grid in which north-south streets, separated by gaps of 10 miles each, 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.

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*v2 mpg. In a given grid of streets we would like to travel from intersection (xs, ys) to intersection (xt, yt). You are to determine the fastest and the most fuel efficient way of making the trip such that:
the car does not change speed between intersections,
the car obeys all speed limits,
the car travels the shortest possible distance between the start and finish, and
the car arrives at the destination in the given time interval.
Input

The first line of input contains an integer t, the number of scenarios to be processed. The data for each scenario occupy 5 lines. The first line contains an integer n<=10 which is the number of horizontal and vertical streets. The second line contains an integer which is the grid unit size in miles, smaller than 100. The third and fourth lines contain n integers each, specifying the speed limits on the horizontal and vertical streets, respectively. The largest speed limit is 50. The last line of data for a scenario contains 6 integers. The first four are xs, ys, xt, and yt. The last two integers give the shortest and the longest allowed time to travel in minutes, inclusive, both not bigger than 1000.
Output

For each scenario, output two or three lines in the format given in the sample output. If the travel is possible then, on the second line of output, report the earliest possible arrival time (but within the imposed limits) and fuel consumed (least possible for this travel time) and, on the third line, report the earliest arrival time (but within the imposed limits) that consumes the minimum amount of fuel. The time is to be reported in minutes (integer), rounded up.
Sample Input

3
8
20
10 20 30 40 50 50 50 50
50 50 50 50 50 50 40 50
2 3 7 8 300 320
8
2
10 20 20 30 10 20 10 10
10 20 20 30 10 20 10 20
6 8 2 4 10 39
10
10
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
Sample Output

Scenario 1:
The earliest arrival: 300 minutes, fuel 6.25 gallons
The economical travel: 318 minutes, fuel 5.60 gallons
Scenario 2:
IMPOSSIBLE
Scenario 3:
The earliest arrival: 405 minutes, fuel 4.14 gallons
The economical travel: 498 minutes, fuel 2.76 gallons

  • 写回答

1条回答 默认 最新

  • devmiao 2017-09-30 01:26
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 arduino控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题