AppleTrees
Member SRM 489 · 2010-03-12 · by rng_58
Problem Statement
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.
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.
10
{40}
Returns: 10
There are 10 candidate positions for the only tree.
4
{1, 1, 1, 1}
Returns: 24
Trees must be planted in different positions, so the number of ways to plant all trees is 4! = 24.
4
{1, 1, 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.
58
{5, 8}
Returns: 2550
47
{4, 8, 9}
Returns: 28830
Submissions are judged against all 72 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class AppleTrees with a public method int theCount(int D, vector<int> r) · 72 test cases · 2 s / 256 MB per case