Problem Statement | | | Rabbit Hanako likes apples. She decided to plant apple trees along a straight road.
The road has D candidate positions for planting apple trees. These positions are numbered 0 through D-1, from left to right. The distance between position x and position y is |x-y| meters (|x-y| denotes the absolute value of x-y). She wants to plant N apple trees numbered from 0 to N-1 in different positions. The trees may be planted in any order. The i-th tree won't grow if there are other trees which are closer than r[i] meters. In other words, if i and j are distinct, the distance between the i-th tree and the j-th tree must be at least max(r[i],r[j]) meters.
Return the number of ways to plant all apple trees modulo 1,000,000,007.
| | | Definition | | | | Class: | AppleTrees | | Method: | theCount | | Parameters: | int, int[] | | Returns: | int | | Method signature: | int theCount(int D, int[] r) | | (be sure your method is public) |
| | | | | | Constraints | | - | D will be between 1 and 100,000, inclusive. | | - | r will contain between 1 and 40 elements, inclusive. | | - | Each element of r will be between 1 and 40, inclusive. | | | Examples | | 0) | | | | | Returns: 10 | | There are 10 candidate positions for the only tree. |
|
| | 1) | | | | | Returns: 24 | | Trees must be planted in different positions, so the number of ways to plant all trees is 4! = 24. |
|
| | 2) | | | | | Returns: 4 | The following 4 ways are possible:
- Plant the 0th tree in position 0, the 1st tree in position 1, and the 2nd tree in position 3.
- Plant the 0th tree in position 1, the 1st tree in position 0, and the 2nd tree in position 3.
- Plant the 0th tree in position 2, the 1st tree in position 3, and the 2nd tree in position 0.
- Plant the 0th tree in position 3, the 1st tree in position 2, and the 2nd tree in position 0.
|
|
| | 3) | | | | | | 4) | | | | | | 5) | | | | 100000 | {21, 37, 23, 13, 32, 22, 9, 39} |
| Returns: 923016564 | |
|
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
|
