NotTwo
SRM 452 · 2009-11-05 · by rng_58
SRM 452 · 2009-11-05 · by rng_58 · Math
Problem Statement
Problem Statement
Bob has a width x height rectangular board divided into 1 x 1 cells. Rows of the board are numbered 0 to height-1 and columns are numbered 0 to width-1.
Each cell can contain at most one stone, and the Euclidean distance between each pair of stones must not equal 2. The Euclidean distance between cell in row x1, column y1 and cell in row x2, column y2 is defined as the square root from (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2).
Return the maximal number of stones he can place on the board.
Each cell can contain at most one stone, and the Euclidean distance between each pair of stones must not equal 2. The Euclidean distance between cell in row x1, column y1 and cell in row x2, column y2 is defined as the square root from (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2).
Return the maximal number of stones he can place on the board.
Constraints
- width will be between 1 and 1000, inclusive.
- height will be between 1 and 1000, inclusive.
Examples
0)
3 2 Returns: 4
He can place four stones on the board. Here is one possible arrangement: - * * * * -
1)
3 3 Returns: 5
* - - * * - - * *
2)
8 5 Returns: 20
3)
1 1 Returns: 1
4)
1 2 Returns: 2
Submissions are judged against all 102 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NotTwo with a public method int maxStones(int width, int height) · 102 test cases · 2 s / 256 MB per case