PerfectRectangles
SRM 431 · 2008-12-23 · by Gluk
SRM 431 · 2008-12-23 · by Gluk · Search
Problem Statement
Problem Statement
You are given a square board of size NxN. Each 1x1 cell will be colored either black or white. A rectangle on the board is called good if it contains only white cells. A good rectangle is called perfect if it doesn't lie completely within any other good rectangle.
Here's how the board will be colored. You are givenint s M, X0, Y0, A, B, C and D. Generate lists X and Y, each of length M, 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
The board is initially entirely white. Then, for each i, the cell in column X[i] of row Y[i] is colored black. Return the number of perfect rectangles on the board.
Here's how the board will be colored. You are given
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
The board is initially entirely white. Then, for each i, the cell in column X[i] of row Y[i] is colored black. Return the number of perfect rectangles on the board.
Notes
- The same cell can be painted black multiple times.
Constraints
- N will be between 1 and 2,000, inclusive.
- M will be between 1 and 4,000,000, inclusive.
- X0,Y0,A,B,C,D will each be between 0 and 2,000, inclusive.
Examples
0)
5 1 2 0 0 2 0 0 Returns: 4
One black cell in the center.
1)
4 4 0 1 1 0 1 1 Returns: 6
Black cells form the diagonal of the square.
2)
1 1000000 1 2 3 1 4 7 Returns: 0
All cells are black.
3)
10 20 4 76 2 6 2 43 Returns: 12
4)
91 2511 440 936 329 467 709 150 Returns: 48
Submissions are judged against all 124 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PerfectRectangles with a public method int numberOfRectangles(int N, int M, int X0, int A, int B, int Y0, int C, int D) · 124 test cases · 2 s / 256 MB per case