Connection Status:
Competition Arena > TreeSpreading

TreeSpreading

SRM 227 · 2005-01-22 · by erinn

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

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.

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
4)
10
10
10
10
Returns: 174702663548149248

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

Coding Area

Language: C++17 · define a public class TreeSpreading with a public method long long countArrangements(int a, int b, int c, int d) · 19 test cases · 2 s / 256 MB per case

Submitting as anonymous