EllysDiggyDiggyHole | Topcoder Archive

Problem Statement

This problem has a non-standard time limit (1 second).

During the Perseids N meteorites (shooting stars) fell into Elly's garden. The girl doesn't like stones in her garden, be it ones with alien origin. Thus, she has decided to dig a hole and throw all of them there.

We will consider Elly's garden to be a square with size M by M feet (M being a power of 2), divided into cells with size 1 by 1 feet. Each cell is indexed with a pair of integers (X_i, Y_i), which represent its column and the row, respectively. The leftmost column is 0, and the rightmost one is M-1. The bottommost row is 0 and topmost one is M-1.

In each cell have fallen zero, one or more meteorites. The hole which Elly will dig will be in one of the cells. If that cell contains meteorites, they fall into the hole immediately without the need for the girl to bring them there. Each other meteorite, though, needs to be brought to the hole and thrown inside.

The girl can go anywhere in the garden (including the cell with the hole). She moves only horizontally or vertically; thus, from a given cell she can move only to one of its (up to four) neighboring cells sharing a side with her current one. Walking without carrying a meteorite doesn't cost her any effort. Since the meteorites are rather heavy, at any given time she can carry at most one of them. Moving a meteorite from a cell to a neighboring one costs her one unit of effort.

Now Elly wonders what is the minimum total effort for moving all meteorites into the hole, if she chooses optimally where it should be.

Since the fallen meteorites are quite many, we will generate the cells where they have fallen in the following way. The first meteorite fell into the cell (X1, Y1). Each sequential one fell in the cell (X_i, Y_i), where X_i = (X_i-1 * A + B) & (M - 1), and Y_i = (Y_i-1 * C + D) & (M - 1), where '&' is the bitwise AND operation.

Definition

Class:: EllysDiggyDiggyHole
Method:: getMin
Parameters:: int, int, int, int, int, int, int, int
Returns:: long
Method signature:: long getMin(int N, int M, int X1, int Y1, int A, int B, int C, int D)
(be sure your method is public)

Constraints

N will be between 1 and 10,000,000, inclusive.
M will be between 1 and 16,777,216, inclusive.
M will be a power of 2 (one of {1, 2, 4, 8, 16, ..., 8388608, 16777216}).
X1, Y1, A, B, C, and D will be between 0 and M-1, inclusive.

Examples

```
6
```
```
16
```
```
5
```
```
10
```
```
13
```
```
1
```
```
5
```
```
5
```
```
Returns: 42
```
The coordinates of the meteorites are: {(5, 10), (2, 7), (11, 8), (0, 13), (1, 6), (14, 3)}. One possible position of the hole, which yields this answer, is (3, 8).
```
20
```
```
128
```
```
34
```
```
39
```
```
5
```
```
96
```
```
80
```
```
13
```
```
Returns: 666
```
Some of the meteorites can fall in the same cell (in this example the cells (18, 29) and (58, 29) contain two each).

Returns: 50901268

16777216

Returns: 10358982811846

Keep in mind that the answer can be rather large.

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.