TopCoder problem "TreePlanting" used in SRM 227 (Division II Level Three)



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.

 

Definition

    
Class:TreePlanting
Method:countArrangements
Parameters:int, int
Returns:long
Method signature:long countArrangements(int total, int fancy)
(be sure your method is public)
    
 

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

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=6516&pm=3515

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Recursion, Simple Math