TopCoder Statistics - Problem Statement

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

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.
10

55

75

5

Returns: 490260662
1

7

8

50

Returns: 72
2

2

36

14

Returns: 2484
3

417

232

43

Returns: 246502024
4

39

28

3

Returns: 2640350
5

40

28

10

Returns: 597
6

40

48

6

Returns: 7956408
7

300

326

5

Returns: 231751905
2

1

1

1

Returns: 6
8

496

438

39

Returns: 446208395
9

2

36

4

Returns: 2145
10

317

82

15

Returns: 234329616
11

39

28

4

Returns: 0
12

40

28

4

Returns: 0
13

40

48

2

Returns: 227955713
14

250

326

24

Returns: 457474184
15

388

163

15

Returns: 994478308
16

500

48

11

Returns: 206739693
17

494

14

23

Returns: 611184520
18

60

58

2

Returns: 172610472
19

2

58

4

Returns: 0
20

222

105

10

Returns: 585030272
21

458

14

21

Returns: 822102050
22

16

42

1

Returns: 841191620
23

228

500

4

Returns: 805903416
24

91

500

7

Returns: 872481282
25

421

312

11

Returns: 424493976
26

289

464

14

Returns: 175093450
27

467

470

15

Returns: 909537996
28

273

23

3

Returns: 451361080
29

427

3

2

Returns: 959744000
30

306

328

3

Returns: 385393404
31

111

252

5

Returns: 378222252
32

193

365

3

Returns: 943182664
33

139

447

6

Returns: 835091520
34

223

207

6

Returns: 337796324
35

225

500

8

Returns: 490522768
36

31

165

3

Returns: 53515776
37

343

403

9

Returns: 517677600
38

478

451

15

Returns: 483173738
39

409

154

2

Returns: 238660604
40

268

477

4

Returns: 371559939
41

268

83

5

Returns: 644090076
42

453

500

4

Returns: 272105444
43

241

461

11

Returns: 284114760
44

450

488

6

Returns: 325459699
45

494

59

9

Returns: 531469792
46

209

500

4

Returns: 73027340
47

390

500

10

Returns: 844183312
48

500

500

13

Returns: 776440460
49

107

5

2

Returns: 200751800
50

370

455

9

Returns: 918208088
50

439

500

1

Returns: 892203494
50

126

494

7

Returns: 176144876
50

76

181

3

Returns: 935538828
50

455

447

12

Returns: 599741912
50

312

37

4

Returns: 370205520
50

430

154

6

Returns: 788385595
50

500

240

5

Returns: 105571448
50

13

499

9

Returns: 230426224
50

455

143

5

Returns: 52964602
50

99

84

2

Returns: 4479
50

500

500

12

Returns: 17751284
50

500

500

13

Returns: 920638408
50

500

500

14

Returns: 920625772
50

500

500

15

Returns: 0
50

500

500

16

Returns: 0
30

500

500

23

Returns: 29891264
30

500

500

24

Returns: 29890080
30

500

500

25

Returns: 0
15

500

500

47

Returns: 126734328
15

500

500

49

Returns: 14709420
15

500

500

50

Returns: 0
2

2

2

2

Returns: 16
2

500

500

2

Returns: 499624500
1

5

5

1

Returns: 36
1

251

497

2

Returns: 125496
1

500

500

50

Returns: 251001
50

500

500

2

Returns: 911709884
1

2

2

1

Returns: 9
30

500

500

27

Returns: 0

Statistics

Problem Statement for "BackyardTrees"

Problem Statement

Definition

Constraints

Examples