BackyardTrees
SRM 328 · 2006-11-29 · by _efer_
Problem Statement
Your backyard is a rectangular grid that measures width x height square meters. You would like to plant treeCount trees using the following rules:
- All trees must be planted at integer coordinates on the grid.
- All trees must lie on the same straight line.
- Each pair of trees must be at least distance meters away from each other.
For example, two (of many) ways in which four trees could be planted on a 10x10 grid if distance is 2 are depicted below:
Return the number of distinct ways in which the trees could be planted, modulo 1,000,000,000. Two layouts are considered distinct if there exists a point (x, y) such that one layout contains a tree at (x, y) and the other layout does not.
Constraints
- treeCount will be between 1 and 50, inclusive.
- width will be between 1 and 500, inclusive.
- height will be between 1 and 500, inclusive.
- distance will be between 1 and 50, inclusive.
2 4 4 1 Returns: 300
There are only two trees, and the distance between any two points with integer coordinates is always at least 1. Therefore, you can place the two trees at any two points with integer coordinates. There are 25 such points and this gives you 300 different ways to plant the trees.
13 36 48 5 Returns: 2
The diagonal of the backyard has a length of 60, which is just enough to place 13 trees with a distance of 5 between each adjacent pair. Luckily, these 13 points are at integer coordinates, so you can place the trees along either of the two diagonals while satisfying all the rules.
5 5 5 1 Returns: 88
50 49 49 1 Returns: 102
You can place the trees along the rows or the columns of the grid, as well as on the two diagonals.
6 5 5 2 Returns: 0
You can't plant 6 trees on the same line with the necessary distance between them on this grid.
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BackyardTrees with a public method int countWays(int treeCount, int width, int height, int distance) · 86 test cases · 2 s / 256 MB per case