ChristmasTree

SRM 331 · 2006-12-21 · by slex

SRM 331 · 2006-12-21 · by slex · Brute Force

Show categories

Class Name: ChristmasTree

Return Type: long

Method Name: decorationWays

Arg Types: (int, int, int, int)

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 int N, the number of levels in the tree, and ints red, green and blue, representing the number of available baubles in each color. Return the number of distinct correct ways to decorate the tree. Two decorated trees are different if there is at least one position at which the two trees have a different colored bauble. If it is impossible to decorate the tree with the given baubles, return 0.

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

13)

3
2
2
1
Returns: 0

You have only five baubles, while six are needed to cover three levels.

14)

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.

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

Coding Area

Language: C++17 · define a public class ChristmasTree with a public method long long decorationWays(int N, int red, int green, int blue) · 54 test cases · 2 s / 256 MB per case