PROBLEM STATEMENT
Salesman Joe does a lot of travelling. He's very brilliant, and has already
solved the Traveling Salesman Problem in linear time and thus knows exactly how
far he has to travel within a given block of time. However, when it comes to
tires for his car, he's no genius. He's done preliminary research, and has
determined the cost of several tires and their mileage warranties. From this
data, you must determine what the minimum cost is to travel the specified
number of miles. Joe, having extreme customer loyalty, wants to choose one
brand of tires and stick with it until he's done with his trip.
The status of the tires at the end of the warranty does not matter, and they
must be replaced. Also, if the tires wear out or are punctured prematurely
(before the warranty expires), they are replaced for free.
Given the cost and warranty for each of several different brands of tires, and
the number of miles to be driven, determine the minimum tire cost.
DEFINITION
Class name: Driver
Method name: minTireCost
Parameters: int[], int[], int
Returns: int
Method signature (be sure your method is public):
int minTireCost(int[] tirecost, int[] warranty, int miles)
TopCoder will enforce the following restrictions:
* There will be between 1 and 20 elements inclusive in tirecost and warranty.
* There will be the same number of elements in tirecost and warranty.
* Each element in warranty will be between 1 and 100000, inclusive.
* Each element in tirecost will be between 1 and 1000, inclusive.
* miles will be between 0 and 1000000, inclusive.
Note that if miles = 0, no tires need to be purchased, thus the method returns
0.
EXAMPLES
Example #1:
tirecost = {400, 300, 200}
warranty = {50000, 40000, 30000}
miles = 100000
Using brand #1 (cost = 400, warranty = 50000),
We require two sets of tires to travel 100000 miles.
The second set will expire exactly as the trip is over, so a third set is not
required.
Thus, this costs 400 * 2 = 800.
Using brand #2 (cost = 300, warranty = 40000),
We require 3 sets of tires. The first expires at 40000 miles, the second at
80000 miles, and the trip is completed in the midst of the third set.
Cost = 300 * 3 = 900.
Using brand #3 (cost = 200, warranty = 30000),
We require 4 sets of tires. The first expires at 30000, 2nd at 60000, 3rd at
90000, and the trip ends in the midst of the 4th set.
Cost = 200 * 4 = 800.
So the minimum cost is min(800, 900, 800) = 800, and the method returns 800
Example #2:
tirecost = {500, 300, 200}
warranty = {50000, 40000, 30000}
miles = 110000
Using brand #1, we have a cost of 3 * 500 = 1500
Using brand #2, we have a cost of 3 * 300 = 900
Using brand #3, we have a cost of 4 * 200 = 800
Thus, the method returns 800
Example #3:
tirecost = {100, 101, 200, 201}
warranty = {20000, 21000, 39000, 40000}
miles = 40001
Method returns 202.