# Travel planning algorithm CHALLENGE!

**Languages that can be used:

c, java, cpp, cc** **to be compiled in UNIX platform - so please make sure they compile on a unix compiler (such as gcc) before submitting the final version to me.**

**The Challenge!**

There is a city whose streets are arranged in a grid in which north-south, east-west streets are separated by gaps of 10miles each. As shown in the above diagram

All streets are two-way. Entrance and exit ramps connect the streets at every intersection.

The speed limits are separately posted for each street and are the same for the entire street in both directions.(10, 20, 30...60mph)

In the illustration above, the southwestern corner of the grid is (1, 1), the southeastern corner is (6, 1), and so on.

Fuel consumption of a car is given in miles-per-litre (mpl) and depends on speed of the car.

Speed of a car is given in mile-per-hour (mph) and is always a positive integer multiple of 5.

The formula relating mpl(mile-per-litre) to mph (mile-per-hour) is a very simple one:

**A car travelling at *v* mph makes 80 - 0.03 **v*2 mpl.**

In a given grid of streets we would like to travel from intersection (*xs*,*ys*) to intersection (*xt*, *yt*).

## Deliverables

You have to develop a program to determine 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 within a specified travel interval.

An intersection means a point in the grid where two streets meet. For example, the point where 2nd horizontal street and 5th vertical street is an intersection which is defined as (5,2).

A car will travell at the same speed between two adjacent intersections. In the given example, the car may travel at a speed 10 mph between (2,2) and (2,3) which is an interval of the 2nd vertical street. The car can then travel a speed 15 mph between (2,3) and (2,4), and then travel a speed 10 mph between (2,4) and (3,4), .... etc.

### Input

The data 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 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

The output consists of one line in the format given in the sample outputs.

If the travel is possible then the output reports 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.

If the travel is not possible, then the output contains a single word IMPOSSIBLE.

### Example DATA

------------

#### 1.0 Input:

8

20

10 20 30 40 50 50 50 50

50 50 50 50 50 50 40 50

2 3 7 8 300 320

####

1.0 Output:

The economical travel: 318 minutes, fuel 5.60 liters

------------

#### 2.0 Input

8

2

10 20 20 30 10 20 10 10

10 20 20 30 10 20 10 20

6 8 2 4 10 39

#### 2.0 Output

IMPOSSIBLE

------------

#### 3.0 Input

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

#### 3.0 Output

The economical travel: 498 minutes, fuel 2.76 liters

------------

All code must be **well commented** with a short description of functions implemented.

Please only bid if you are ready for this challenge and can implement the solution in time. Its really straight forward, just requires a bit of thinking.

### An extra \$\$\$ bonus will also be paid to the bidder if the solution is impressive!

Only bid on this if you are sure you can implement the CORRECT solution.

## Platform

Deliverables must be in ready-to-run condition, as follows (depending on the nature of the deliverables):

All deliverables will be considered "work made for hire" under U.S. Copyright law. Buyer will receive exclusive and complete copyrights to all work purchased. (No GPL, GNU, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site per the coder's Seller Legal Agreement).

Unix, Linux ONLY. Please make sure your program compiles on a unix compiler!

Evner: C programmering, Java, PHP

Om arbejdsgiveren:
( 17 bedømmelser ) Meadowbank, Australia

Projekt ID: #3407868

## Tildelt til:

IanHeggie

See private message.

\$17 USD in 3 dage
(1 bedømmelse)
0.5

## 18 freelancere byder i gennemsnit \$31 på dette job

navol

See private message.

\$39.95 USD in 3 dage
(109 bedømmelser)
6.1
mkoutsourcing

See private message.

\$42.5 USD in 3 dage
(43 bedømmelser)
5.9
rainbow

See private message.

\$42.5 USD in 3 dage
(25 bedømmelser)
5.3
senzaciosnegyes

See private message.

\$32.3 USD in 3 dage
(104 bedømmelser)
4.9
chris0746

See private message.

\$38.25 USD in 3 dage
(21 bedømmelser)
4.8
santon

See private message.

\$29.75 USD in 3 dage
(40 bedømmelser)
4.8
hmmvw

See private message.

\$42.5 USD in 3 dage
(24 bedømmelser)
4.4
crcconsultingvw

See private message.

\$21.25 USD in 3 dage
(23 bedømmelser)
4.3
ralub

See private message.

\$25.5 USD in 3 dage
(35 bedømmelser)
4.2
hmichopoulos

See private message.

\$29.75 USD in 3 dage
(27 bedømmelser)
3.7
sooska

See private message.

\$38.25 USD in 3 dage
(6 bedømmelser)
3.0
ellipsesvw

See private message.

\$17 USD in 3 dage
(15 bedømmelser)
2.5
Smoker

See private message.

\$25.5 USD in 3 dage
(1 bedømmelse)
1.0
milojkovw

See private message.

\$25.5 USD in 3 dage
(3 bedømmelser)
0.4
bellatrixvw

See private message.

\$34 USD in 3 dage
(0 bedømmelser)
0.0
blackzerovw

See private message.

\$34 USD in 3 dage
(0 bedømmelser)
0.0
jkillervw

See private message.

\$29.75 USD in 3 dage
(0 bedømmelser)
0.0