RoadOrFlightHard | Topcoder Archive

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
Method signature:: long minTime(int N, int roadFirst, int roadProd, int roadAdd, int roadMod, int flightFirst, int flightProd, int flightAdd, int flightMod, int K)
(be sure your method is public)

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

```
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.

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)2024, Topcoder, Inc. All rights reserved.