EllysTeleport
TCO19 Round 1B · 2019-04-15 · by espr1t
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
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.
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
1000 1337 706135 1085680 1153206 345473 1234567 Returns: 42
Watch out for overflows when generating the heights!
Submissions are judged against all 127 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class EllysTeleport with a public method int getMax(int N, int H1, int A, int B, int P, int Q, int M) · 127 test cases · 2 s / 256 MB per case