TopCoder problem "TreeSpreading" used in SRM 227 (Division I Level Two)



Problem Statement

    

A farmer is planting a line of trees across the front of his house. He has four different kinds of trees he would like to plant. However, for aesthetic reasons, he does not want two of the same type of tree next to each other. Beyond that, any arrangement of trees is considered acceptable.

You are given ints a, b, c, and d, indicating how many of each type of tree the farmer is going to plant. You are to return a long indicating the number of acceptable ways in which the trees can be ordered.

 

Definition

    
Class:TreeSpreading
Method:countArrangements
Parameters:int, int, int, int
Returns:long
Method signature:long countArrangements(int a, int b, int c, int d)
(be sure your method is public)
    
 

Notes

-Each tree of a given type is identical to others of the same type, thus swapping the positions of two of the same type of tree does not consitute a new arrangement.
 

Constraints

-a, b, c, and d will be between 0 and 10, inclusive.
 

Examples

0)
    
1
1
0
0
Returns: 2
There are only two trees to place, and they can go in either order.
1)
    
2
2
0
0
Returns: 2
There are two possible arrangements: ABAB or BABA. Any others have two identical trees adjacent to one another.
2)
    
1
1
1
1
Returns: 24
Since all four trees are different, they can be arranged in any order, so the answer is 4!.
3)
    
3
2
1
1
Returns: 96

Problem url:

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

Problem stats url:

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

Writer:

timmac

Testers:

PabloGilberto , lbackstrom , brett1479

Problem categories:

Dynamic Programming, Simple Math, Simple Search, Iteration