CatchTheBeat

SRM 623 · 2013-12-22 · by cgy4ever

SRM 623 · 2013-12-22 · by cgy4ever · Dynamic Programming, Geometry

Show categories

Class Name: CatchTheBeat

Return Type: int

Method Name: maxCatched

Arg Types: (int, int, int, int, int, int, int, int, int, int)

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.

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.

The only fruit is located at (-1000, 1234). We can go to (-1000, 0) and then wait for 234 seconds to catch it.

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.

Watch out for integer overflow when generating the coordinates.

Submissions are judged against all 147 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class CatchTheBeat with a public method int maxCatched(int n, int x0, int y0, int a, int b, int c, int d, int mod1, int mod2, int offset) · 147 test cases · 2 s / 256 MB per case