Connection Status:
Competition Arena > TreePlanting

TreePlanting

SRM 227 · 2005-01-22 · by erinn

SRM 227 · 2005-01-22 · by erinn · Dynamic Programming, Recursion, Simple Math
Class Name: TreePlanting
Return Type: long
Method Name: countArrangements
Arg Types: (int, int)
Problem Statement

Problem Statement

A farmer wants to plant a row of trees along the front of his house. He has two different kinds of trees, some which are plain looking, and other, more expensive, fancy trees. He wishes to plant the trees in such a way that not all of the fancy trees are grouped together, so he insists that no two fancy trees be adjacent to one another.

You are given an int total indicating the total number of trees to be planted, and an int fancy which is the number of fancy trees. You are to return a long indicating the number of possible tree arrangements that meet the farmer's criteria of having no two fancy trees adjacent to one another.

Notes

  • You may assume that each fancy tree is identical to one other, and likewise for the plain trees.
  • If no valid arrangements are possible, the return value should be 0.

Constraints

  • total will be between 1 and 60, inclusive.
  • fancy will be between 1 and 60, inclusive.
  • fancy will be less than or equal to total.
Examples
0)
4
2
Returns: 3

Here, we have two plain trees, and two fancy trees. There are only three acceptable arrangements: PFPF, FPPF or FPFP. Any other arrangement would have two fancy trees next to each other.

1)
3
1
Returns: 3

There is only one fancy tree, and it can go in any of three locations.

2)
4
3
Returns: 0

There is no way to place all three fancy trees without two of them being next to each other.

3)
10
4
Returns: 35
4)
60
17
Returns: 686353797976

Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class TreePlanting with a public method long long countArrangements(int total, int fancy) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous