ThreeDChessRooks

A 3D chessboard is a C x C x C cube. Rows, columns and floors are each numbered from 0 to C-1, inclusive.

A rook in 3D chess moves like a rook in traditional chess, except now we have six possible cardinal directions instead of four. When moving a rook we choose one of those six directions and move the rook a positive number of steps in the chosen direction. During the move the rook can only traverse through empty cells. The rook may end its move in a cell that contains a chess piece of the opposite color; that piece is then captured by the rook and removed from the board.

You are given a collection of R (not necessarily distinct) cells of the 3D chessboard. The cells in the collection are numbered from 0 to R-1, inclusive. Cell i has coordinates (X[i], Y[i], Z[i]). In order to keep the input size small, only a prefix of the coordinates is actually given, the rest will be pseudorandom.

Consider the following interaction:

1. Wanda selected an index i (0 <= i <= R-1) and placed a white rook into cell i.
2. Boris selected an index j (0 <= j <= R-1, cells i and j are not the same cell) and placed a black rook into cell j.
3. Wanda made a valid move with her rook without capturing Boris's rook.
4. Boris made a valid move with his rook and captured Wanda's rook with that move.

Count all ordered pairs (i, j) for which the above interaction could take place. Return that count.

The arrays X, Y and Z are defined as follows:

---------------------------------------------------------

Pseudocode:

L = length(XP)
for i = 0 to L-1:
    X[i] = XP[i]
    Y[i] = YP[i]
    Z[i] = ZP[i]

state = seed
for i = L to R-1:
    state = (state * 1103515245 + 12345) modulo 2^31
    X[i] = state modulo C
    state = (state * 1103515245 + 12345) modulo 2^31
    Y[i] = state modulo C
    state = (state * 1103515245 + 12345) modulo 2^31
    Z[i] = state modulo C

---------------------------------------------------------

C++:

vector<int> X(R), Y(R), Z(R);

int L = XP.size();
for (int i=0; i<L; ++i) { X[i]=XP[i]; Y[i]=YP[i]; Z[i]=ZP[i]; }

long long state = seed;
for (int i=L; i<R; ++i) {
    state = (state * 1103515245 + 12345) % (1LL << 31);
    X[i] = state % C;
    state = (state * 1103515245 + 12345) % (1LL << 31);
    Y[i] = state % C;
    state = (state * 1103515245 + 12345) % (1LL << 31);
    Z[i] = state % C;
}

---------------------------------------------------------

Java:

int[] X = new int[R];
int[] Y = new int[R];
int[] Z = new int[R];

int L = XP.length;
for (int i=0; i<L; ++i) { X[i]=XP[i]; Y[i]=YP[i]; Z[i]=ZP[i]; }

long state = seed;
for (int i=L; i<R; ++i) {
    state = (state * 1103515245 + 12345) % (1L << 31);
    X[i] = (int)(state % C);
    state = (state * 1103515245 + 12345) % (1L << 31);
    Y[i] = (int)(state % C);
    state = (state * 1103515245 + 12345) % (1L << 31);
    Z[i] = (int)(state % C);
}