BlackBoxDiv2
SRM 602 · 2013-11-22 · by snuke
SRM 602 · 2013-11-22 · by snuke · Math
Problem Statement
Problem Statement
Cat Upper has a rectangular black box.
On the bottom of the box there is a grid that divides the box into identical square cells.
There are no walls between the cells.
The sides of the box are transparent, the top and bottom are opaque (i.e., Upper cannot see through them).
Some of the cells are filled: each of them contains an opaque black block that fills the entire cell.
The remaining cells are empty.
Cat Upper looked into the black box from the front and recorded what he saw: Whenever a column of the grid was completely empty, he could see through the box and wrote down '.' (a period). And whenever a column of the grid contained at least one block, Upper could not see through the box and he wrote down 'B'.
Then, he looked into the black box from the left side and again he recorded what he saw: for each row of the grid he wrote '.' if the row was completely empty and 'B' otherwise.
You are given the recorded information in twoString s: front and side.
Return the number of possible arrangements of the opaque blocks within the black box, modulo 1,000,000,007. Note that you don't know the exact number of blocks in the black box.
Cat Upper looked into the black box from the front and recorded what he saw: Whenever a column of the grid was completely empty, he could see through the box and wrote down '.' (a period). And whenever a column of the grid contained at least one block, Upper could not see through the box and he wrote down 'B'.
Then, he looked into the black box from the left side and again he recorded what he saw: for each row of the grid he wrote '.' if the row was completely empty and 'B' otherwise.
You are given the recorded information in two
Return the number of possible arrangements of the opaque blocks within the black box, modulo 1,000,000,007. Note that you don't know the exact number of blocks in the black box.
Constraints
- front and side will each contain between 1 and 50 characters, inclusive.
- Each character in front and side will be 'B' or '.'.
Examples
0)
"BB" "BB" Returns: 7
There are seven possible arrangements, as shown in the figure below.
1)
"..." "....." Returns: 1
There is no block, thus there is exactly 1 valid arrangement: the one where all cells are empty.
2)
"..." "BBB" Returns: 0
There is no possible arrangement. Upper must have made a mistake.
3)
"...BB.B...." "B.B.B.B.B" Returns: 16081
4)
"BBBBB.BBBBBBBBB.BBBBBBB.BBBB.B.BB..BB.B.BBBBBBBBBB" ".B.BBB..BBBBBB.BBBB.B...BBBB.BB.BBBBBBBBBB.....BBB" Returns: 771030153
Submissions are judged against all 63 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BlackBoxDiv2 with a public method int count(string front, string side) · 63 test cases · 2 s / 256 MB per case