RoadOrFlightHard
Member SRM 468 · 2009-12-03 · by keshav_57
Problem Statement
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.
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.
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.
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.
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.
331999 65645 48613 81333 82122 2374 18997 3468 97383 10 Returns: 13625973966
337552 12367 19281 79400 76410 29402 38052 12277 1125 27 Returns: 187902412
Submissions are judged against all 133 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RoadOrFlightHard with a public method long long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K) · 133 test cases · 2 s / 256 MB per case