PROBLEM STATEMENT
You have been given a new vehicle to test drive. It is extremely fast and uses
up gas even faster. Given trip specifications you are to determine the least
amount of gas needed to complete the trip.
You will be given a list of landmarks. Your trip will start at the westmost
landmark, visit all the other landmarks on the map, and then will return to the
westmost landmark. The problem is, your car is so fast it doesn't turn very
well. Due to this, your trip must be divided into exactly two parts: the
eastward trip, and the westward trip. On the eastward trip you are only
allowed to go to landmarks that take your further east. On the westward trip
you are only allowed to go to landmarks that take your further west. This
means the last landmark visited on the eastward trip must be the eastmost
landmark.
The distance from one landmark to another is their distance in Cartesian
coordinates:
D = sqrt((x2-x1)^2 + (y2-y1)^2) where D is the distance from point (x1,y1) to
(x2,y2).
A car's fuel-to-distance ratio will give how much fuel is used per unit of
distance traveled. To find the amount of fuel consumed in the direct trip from
(x1,y1) to (x2,y2) you calculate: F = D*R where D is the distance as calculated
above and R is the given fuel-to-distance ratio. Note, fuel need not be
consumed in integral amounts.
We want to find the least amount of gas needed, so you must take the shortest
possible trip given the previously stated constraints. The returned gas value
is an integral amount so round results up to the nearest integer. Note,
rounding occurs after you calculate the amount of gas. To prevent rounding
errors, TopCoder will ensure that the solution (before rounding) will not be
within .001 of the nearest integer.
Create a class GasRacing that contains the method numTrips, which takes an
int[] xs, int[] ys, and an int ratio and returns an int giving the least amount
of gas needed to make the trip.
DEFINITION
Class: GasRacing
Method: leastGas
Parameters: int[], int[], int
Returns: int
Method signature (be sure your method is public): int leastGas(int[] xs, int[]
ys, int ratio);
NOTES
- Landmark K has x-coordinates xs[K] and y-coordinate ys[K]
- There are 50 potential landmarks so make sure your algorithm is efficient
- Traveling westward means your x-coordinate is decreasing whereas traveling
eastward means your x-coordinate is increasing
- Fractional answers must be rounded up to the nearest integer
- The trip begins at the westmost landmark
HINTS
- Two way to solve this problem
1) Dynamic programming (previously stored results will help)
2) Divide and conquer (something like how merge sort works)
- The fact that the trip must be completely divided into 2 parts (eastward and
westward) is very helpful in finding the solution
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- xs and ys will contain the same number of elements
- xs and ys will contain between 2 and 50 elements inclusive
- xs will contain no repeated values
- Each element of xs will be between -1000 and 1000 inclusive
- Each element of ys will be between -1000 and 1000 inclusive
- ratio will be between 1 and 100 inclusive
- The solution (prior to rounding up to the nearest integer) will not be within
.001 of the nearest integer (solution < int - .001 or solution > int + .001)
EXAMPLES
'X's are used to denote the coordinate axes
'.'s are used to denote the landmarks
'/'s,'\'s, and '-'s are used to denote the path taken.
1) xs = {0,2,3,4,6}
ys = {0,2,0,2,0}
ratio = 2
The best trip looks like:
X
X .-.
X/ \
XXXX.--.--.
X
X
X
The diagram above doesn't have arrows on it but they could be added. We could
start at the origin and take the upper path east, followed by taking the lower
path west. We could also start at the origin and take the lower path east,
after which taking the upper path west. Both paths produce the same result.
The distance of this trip is about 13.657 so the gas required is 2*13.657 =
27.314.
We round up to the nearest integer so the method returns 28.
2) xs = {0,4,2,9}
ys = {0,4,-2,-2}
ratio = 1
The best trip looks like:
X .
X / \
X / \
X/ \
XXXX.XXXXXXX\X
X\ \
X .------.
X
The diagram above doesn't have arrows on it but they could be added. We could
start at the origin and take the upper path east, followed by taking the lower
path west. We could also start at the origin and take the lower path east,
after which taking the upper path west. Both paths produce the same result.
The distance of this trip is about 23.296 so the gas required is 1*23.296 =
23.296.
We round up to the nearest integer so the method returns 24.
3) xs = {0,4,2,9}
ys = {0,4,-2,-2}
ratio = 100
Same trip but a different ratio. 100*23.296 = 2329.6.
We round up to the nearest integer so the method returns 2330.
4) xs = {-1000,1000}
ys = {-1000,1000}
ratio = 99
Method returns 560029.
5) xs = {145,238,-123,42,54,235,-173,934,-934,234}
ys = {234,532,593,994,-992,123,324,234,100,1000}
ratio = 99
Method returns 640569.