EllysTeleport | Topcoder Archive

Problem Statement

Elly plays a platform game on her computer. There are N platforms with distinct heights, placed on top of each other. You can generate the heights of the platforms as follows:

Platform number 1 is has height[1] = H1.
For each i between 2 and N, inclusive, height[i] = (height[i-1] * A + B) % M.

The girl has a "hero" whom she can move from platform to platform. At the beginning of the game there is a coin on each platform. The hero collects the coin the first time she visits the platform. (Once a coin is collected, it is gone. Visiting the same platform again does not give Elly a second coin.)

In the beginning of the game Elly can place her hero on any of the N platforms. Once she does that, the hero will pick up the coin from that platform and then the game starts.

During the game Elly only has one way to move her hero: by using a device that teleports the hero vertically. The device is deterministic and it behaves as follows: if the hero's current platform is at height X, the hero gets teleported to the height Y = (X * P + Q) % M. After the teleport, one of three different things will happen:

If there is a platform at height Y, the hero will stand on that platform and collect the coin from that platform (if it is still there).
If there is no platform at height Y but there are some lower platforms, the hero falls down until she hits the closest platform. She will always lands safely, regardless of the height of the fall. Then, she will collect the coin from that platform (if it is still there).
If there are no platforms at or below the hero's new height, the game ends.

Elly can use the device arbitrarily many times, one after another. Note that the device can only be used while the hero is standing on a platform (i.e., not while she is falling).

You are given all the ints mentioned in the problem statement. Compute and return the largest number of coins Elly's hero can collect during a single game.

Definition

Class:: EllysTeleport
Method:: getMax
Parameters:: int, int, int, int, int, int, int
Returns:: int
Method signature:: int getMax(int N, int H1, int A, int B, int P, int Q, int M)
(be sure your method is public)

Constraints

N will be between 1 and 10,000, inclusive.
M will be between 1 and 1,000,000,007, inclusive.
H1, A, B, P and Q will be between 0 and M-1, inclusive.
All platform heights will be distinct.

Examples

```
11
```
```
9
```
```
17
```
```
9
```
```
7
```
```
13
```
```
23
```
```
Returns: 6
```
The generated heights are {9, 1, 3, 14, 17, 22, 15, 11, 12, 6, 19}. The optimal choice would be to start from the platform with height 15. The heights Elly's hero will visit are: 15 -> 3 -> 11 -> [21] -> 19 -> [8] -> 6 -> 9 -> [7] -> 6... With [Y] we have denoted a height where the hero is teleported to, but there is no platform so she starts falling down.
```
8
```
```
17
```
```
23
```
```
19
```
```
15
```
```
28
```
```
43
```
```
Returns: 4
```
The generated numbers are {17, 23, 32, 24, 12, 37, 10, 34}. There are two possible choices for a starting platform, which yields the maximal number of coins: 32 or 12 (the paths being, respectively, 32 -> [35] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1] -> game ends, and 12 -> [36] -> 34 -> [22] -> 17 -> [25] -> 24 -> [1] -> game ends).
```
15
```
```
42
```
```
114
```
```
52
```
```
76
```
```
1
```
```
131
```
```
Returns: 5
```
The generated numbers are {42, 124, 40, 27, 117, 28, 100, 55, 34, 129, 86, 31, 49, 5, 98}.
```
10
```
```
71
```
```
54
```
```
85
```
```
96
```
```
52
```
```
100
```
```
Returns: 10
```
Here the heights are {71, 19, 11, 79, 51, 39, 91, 99, 31, 59}. Starting from the platform with height 99 Elly's hero can collect all of the coins: 99 -> [56] -> 51 -> [49] -> 39 -> [96] -> 91 -> [88] -> 79 -> [36] -> 31 -> [28] -> 19 -> [76] -> 71 -> [68] -> 59 -> [16] -> 11 -> [8] -> game ends

Returns: 42

Watch out for overflows when generating the heights!

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.