CatchTheBeat | Topcoder Archive

Problem Statement

One of the modes in the game "osu!" is called "catch the beat". In this mode, you control a character that catches falling fruit.

The game is played in the vertical plane. For simplicity, we will assume that both your character and all pieces of fruit are points in that plane.

You start the game at the coordinates (0, 0). Your character can only move along the x-axis. The maximum speed of your character is 1 unit of distance per second. For example, you need at least 3 seconds to move from (-2, 0) to (1, 0).

There are n pieces of fruit. The pieces are numbered 0 through n-1. For each i, fruit i starts at (x[i], y[i]). All pieces of fruit fall down with constant speed of 1 unit of distance per second. That is, a fruit currently located at (xf, yf) will move to (xf, yf-t) in t seconds. You will catch a fruit if the character is located at the same point as the fruit at some moment in time.

The initial coordinates x[] and y[] are generated using the following pseudocode:

x[0] = x0
for i = 1 to n-1:
    x[i] = (x[i-1] * a + b) % mod1

for i = 0 to n-1:
    x[i] = x[i] - offset

y[0] = y0
for i = 1 to n-1:
    y[i] = (y[i-1] * c + d) % mod2

(In the pseudocode, '%' represents the 'modulo' operator.)

You are given all the ints used in the above pseudocode. Return the maximum number of pieces of fruit you can catch.

Definition

Class:: CatchTheBeat
Method:: maxCatched
Parameters:: int, int, int, int, int, int, int, int, int, int
Returns:: int
Method signature:: int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset)
(be sure your method is public)

Constraints

n will be between 1 and 500,000, inclusive.
mod1 and mod2 will be between 1 and 1,000,000,000, inclusive.
x0, a and b will be between 0 and (mod1 - 1), inclusive.
y0, c and d will be between 0 and (mod2 - 1), inclusive.
offset will be between 0 and 1,000,000,000, inclusive.

Examples

```
3
```
```
0
```
```
0
```
```
1
```
```
1
```
```
1
```
```
1
```
```
100
```
```
100
```
```
1
```
```
Returns: 2
```
There are 3 pieces of fruit. Their initial coordinates are (-1, 0), (0, 1), and (1, 2). Clearly you cannot catch fruit 0. You can catch the other two. One way of doing so: Wait at (0, 0) for 1 second. Catch fruit 1. Move to (1, 0) in 1 second. Immediately catch fruit 2.
```
1
```
```
0
```
```
1234
```
```
0
```
```
0
```
```
0
```
```
0
```
```
1000000000
```
```
1000000000
```
```
1000
```
```
Returns: 1
```
The only fruit is located at (-1000, 1234). We can go to (-1000, 0) and then wait for 234 seconds to catch it.
```
1
```
```
0
```
```
999
```
```
0
```
```
0
```
```
0
```
```
0
```
```
1000000000
```
```
1000000000
```
```
1000
```
```
Returns: 0
```
Now the only fruit is located at (-1000, 999). We can't catch it.
```
100
```
```
0
```
```
0
```
```
1
```
```
1
```
```
1
```
```
1
```
```
3
```
```
58585858
```
```
1
```
```
Returns: 66
```
```
500000
```
```
123456
```
```
0
```
```
1
```
```
0
```
```
1
```
```
1
```
```
1000000000
```
```
1000000000
```
```
0
```
```
Returns: 376544
```
The fruits are located in (123456, 0), (123456, 1), ..., (123456, 499999).
```
500000
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
0
```
```
1
```
```
1
```
```
0
```
```
Returns: 500000
```
In this case all the fruits start at (0, 0). Note that there can be more than one fruit at any position. We can catch all such fruit at the same time.

999999957

993948167

24597383

212151897

999940854

999999986

999940855

Returns: 3

Watch out for integer overflow when generating the coordinates.

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.