BlackAndWhiteBallsEasy
SRM 777 · 2020-01-26 · by Witaliy
Problem Statement
Some black and some white balls are placed in a row.
You are given a
- At the beginning there are balls[0] white balls.
- Then there are balls[1] black balls.
- After those there are balls[2] white balls again.
- ... and so on, alternating between white and black.
You have to split the entire row into segments. Each segment must be labeled either "white" or "black". A segment labeled "white" must contain exactly white white balls (and arbitrarily many black ones). A segment labeled "black" must contain exactly black black balls (and arbitrarily many white ones).
Find the number of ways in which we can split the row into segments and assign colors to those segments. Return that value modulo 1,000,000,007.
Constraints
- balls will contain between 1 and 50 elements, inclusive.
- Each element of balls will be between 1 and 50, inclusive.
- white and black will be between 1 and 50, inclusive.
{2, 2}
1
2
Returns: 4
The row of balls looks as follows: WWBB. The four ways to split it are listed below. White segment W, white segment W, black segment BB. White segment W, white segment WBB. White segment W, black segment WBB. Black segment WWBB. Note that the second and third way are considered distinct: the division of the row into segments is the same but the labels are not.
{2, 1, 3}
1
1
Returns: 14
{1, 1, 1, 1, 1}
1
1
Returns: 28
{2, 2, 2, 2, 2}
1
1
Returns: 236
{3, 6, 3, 10}
2
3
Returns: 12
Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BlackAndWhiteBallsEasy with a public method int getNumber(vector<int> balls, int white, int black) · 86 test cases · 2 s / 256 MB per case