TopCoder problem "BackyardTrees" used in SRM 328 (Division I Level Three)



Problem Statement

    This problem statement contains images that may not display properly if viewed outside of the applet.

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.

 

Definition

    
Class:BackyardTrees
Method:countWays
Parameters:int, int, int, int
Returns:int
Method signature:int countWays(int treeCount, int width, int height, int distance)
(be sure your method is public)
    
 

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.
 

Examples

0)
    
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.
1)
    
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.
2)
    
5
5
5
1
Returns: 88
3)
    
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.
4)
    
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.
5)
    
10
55
75
5
Returns: 490260662

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6620

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10008&pm=6620

Writer:

_efer_

Testers:

PabloGilberto , brett1479 , Olexiy , lovro

Problem categories:

Dynamic Programming, Recursion, Simple Math, Simple Search, Iteration