Problem Statement
You are decorating your Christmas tree. The tree has N levels, numbered 1 through N from top to bottom. You have a number of red, green and blue baubles, and you've decided to hang them in the following manner: On each level k, you will hang a row of exactly k baubles. Within each row, you will select the colors of the baubles such that there is an equal number of baubles of each color used in that level. For example, consider the following two trees:
R R
B G B G
R R R R B R
The tree on the left is correctly decorated. Each row contains an equal number of baubles for each color used. The tree on the right, however, is not correctly decorated because the third level contains an unequal number of red and blue baubles.
You are given an
Definition
- Class:
- ChristmasTree
- Method:
- decorationWays
- Parameters:
- int, int, int, int
- Returns:
- long
- Method signature:
- long decorationWays(int N, int red, int green, int blue)
- (be sure your method is public)
Constraints
- N will be between 1 and 10, inclusive.
- red will be between 0 and 50, inclusive.
- green will be between 0 and 50, inclusive.
- blue will be between 0 and 50, inclusive.
Examples
1
1
2
0
Returns: 2
1
0
0
0
Returns: 0
2
1
1
1
Returns: 6
You can use any of the three colors for the top bauble, which always leaves you with two choices for the second level. Hence, there is a total of six different ways to decorate the tree: R R B G G B B B R G G R G G B R R B
2
2
1
0
Returns: 3
If you put the green bauble on the top level, you must put both reds on the second level. On the other hand, if you put the red bauble on the top level, you have two different ways to decorate the second level (red-green or green-red). That makes a total of three ways.
2
3
0
0
Returns: 1
2
0
3
0
Returns: 1
2
0
0
3
Returns: 1
2
3
3
3
Returns: 27
2
7
1
0
Returns: 4
3
7
1
0
Returns: 4
3
7
1
1
Returns: 19
3
7
4
3
Returns: 211
3
7
7
7
Returns: 243
3
2
2
1
Returns: 0
You have only five baubles, while six are needed to cover three levels.
3
2
2
2
Returns: 36
The third level must either have three baubles of the same color or three baubles with different colors. Since you don't have three baubles of the same color, you must use three different colors for that level.
4
0
10
0
Returns: 1
4
1
10
1
Returns: 19
4
1
8
1
Returns: 12
4
5
8
0
Returns: 69
4
5
8
5
Returns: 4170
4
10
10
10
Returns: 5103
4
5
0
5
Returns: 18
4
5
1
3
Returns: 0
5
7
4
4
Returns: 258
5
15
0
0
Returns: 1
5
14
1
0
Returns: 3
5
14
1
1
Returns: 18
5
4
10
1
Returns: 141
5
4
10
10
Returns: 7010
6
20
20
20
Returns: 2342274
6
20
0
20
Returns: 5630
7
24
3
1
Returns: 153
7
20
3
5
Returns: 12667
8
1
15
20
Returns: 197121
8
13
15
20
Returns: 519710536
9
13
15
20
Returns: 145192863537
9
23
0
22
Returns: 87463
9
23
1
22
Returns: 795052
9
1
43
1
Returns: 12
9
50
50
50
Returns: 2518971350049
10
50
50
50
Returns: 1911899254684272
10
50
5
0
Returns: 661
10
2
3
50
Returns: 627
10
3
3
49
Returns: 3906
10
0
0
50
Returns: 0
10
25
15
15
Returns: 6125137522902
3
4
1
1
Returns: 12
1
12
12
12
Returns: 3
10
50
50
50
Returns: 1911899254684272
6
50
50
50
Returns: 2342277
10
1
1
1
Returns: 0
9
49
49
49
Returns: 2518971350049
2
1
1
1
Returns: 6
1
1
1
1
Returns: 3