PROBLEM STATEMENT
The king has been out to work for a long time and he wants to go back to his queen as fast as
possible. The king is in city 0 and the queen is in city N. There are roads and flights connecting
city i to city (i+1) for all i between 0 and N-1, inclusive.
The time it takes to travel from city i to city (i+1) by road and by flight is given by the i-th
elements of roadTime and flightTime, respectively. roadTime can be generated from the following
pseudocode:
roadTime[0] = roadFirst mod roadMod;
for i = 1 to N-1
roadTime[i] = (roadTime[i-1]*roadProd + roadAdd) mod roadMod;
// note that (roadTime[i-1]*roadProd + roadAdd) may overflow a 32-bit integer
flightTime can be generated similarly by using flightFirst, flightProd, flightAdd, flightMod.
However, taking a flight risks the life of the king during takeoffs due to the technological
limitations in the kingdom. Hence the queen has asked him to ensure that the total number of
takeoffs during his entire journey does not exceed K.
To minimize the number of takeoffs, the king may choose to take a direct flight from city i to
city i+j instead of separate flights from city i to city i+1, then from i+1 to i+2, ... and from
i+(j-1) to i+j. The time taken for this flight is the sum of the times taken for the flights from
i to i+1, i+1 to i+2, ..., i+(j-1) to i+j.
Return the minimum amount of time in which the king can reach his queen.
DEFINITION
Class:RoadOrFlightHard
Method:minTime
Parameters:int, int, int, int, int, int, int, int, int, int
Returns:long long
Method signature:long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod,
int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
CONSTRAINTS
-N will be between 1 and 400000, inclusive.
-roadFirst, roadAdd, flightFirst and flightAdd will each be between 0 and 100000, inclusive.
-roadProd, roadMod, flightProd and flightMod will each be between 1 and 100000, inclusive.
-K will be between 0 and 40, inclusive.
-K will be less than or equal to N.
EXAMPLES
0)
3
14
1
2
10
18
1
10
17
1
Returns: 14
The pseudocode gives roadTime = {4, 6, 8} and flightTime = {1, 11, 4}. The fastest way to reach
the queen is to take the road from city 0 to 1 and 1 to 2, and a flight from city 2 to 3.
1)
3
4
1
2
10
1
1
10
17
2
Returns: 11
roadTime and flightTime are the same as in previous example. But now the king is allowed 2 takeoffs.
2)
3
4
1
2
10
1
1
6
9
1
Returns: 12
roadTime = {4, 6, 8} and flightTime = {1, 7, 4}. Even though roadTime[1] < flightTime[1], it is
best to take a direct flight from city 0 to city 3 which takes a total time of 1 + 7 + 4 = 12
units.
3)
5
85739
94847
93893
98392
92840
93802
93830
92790
3
Returns: 122365
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.