Problem Statement |
| | You are given a square board of size NxN, where each 1x1 cell is either black or white. A rectangle on the board is called good if it contains only white cells. The score of each cell is equal to the number of distinct good rectangles that contain that cell.
Use the following instructions to determine the coloring of the board. You are given ints M, K, X0, Y0, A, B, C and D. Generate two lists, X and Y, each of length M+K, using the following recursive definitions:
X[0] = X0 MOD N
X[i] = (X[i-1]*A+B) MOD N
Y[0] = Y0 MOD N
Y[i] = (Y[i-1]*C+D) MOD N
For each i between 0 and M-1, inclusive, the cell at column X[i], row Y[i] is black. The remaining cells are white.
Let's denote the score for the cell at column i, row j as score(i, j). Return the sum of score(X[i], Y[i]) for all i between M and M+K-1, inclusive. |
| |
Definition |
| | | Class: | CellScores | | Method: | countScores | | Parameters: | int, int, int, int, int, int, int, int, int | | Returns: | long | | Method signature: | long countScores(int N, int M, int K, int X0, int A, int B, int Y0, int C, int D) | | (be sure your method is public) |
|
| |
|
| |
Constraints |
| - | N will be between 1 and 1,500, inclusive.
|
| - | M and K will each be between 0 and 1,000,000, inclusive.
|
| - | X0,Y0,A,B,C,D will each be between 0 and 1,500, inclusive.
|
| |
Examples |
| 0) | |
| | | Returns: 100 | | The whole board is white. You are interested in cell (0,0). The score for this cell is 100. |
|
|
| 1) | |
| | | Returns: 75 | | Only the cell (5,5) is black. You are interested in cell (0,0). The score for this cell is 75. |
|
|
| 2) | |
| | | Returns: 194 | | The first 4 cells on the diagonal are black, and you are interested in the other 3 cells on the diagonal. |
|
|
| 3) | |
| | |
| 4) | |
| | |
| 5) | |
| | |