RectangleDivision
TCO04 Finals · 2004-09-07 · by lars2520
TCO04 Finals · 2004-09-07 · by lars2520 · Brute Force
Problem Statement
Problem Statement
Consider an a by b rectangle, composed of a*b unit squares. Your task is to count the number of ways in which this rectangle can be divided into two contiguous sections, each consisting of 1 or more unit squares. Each section must contain at least 1 square on the edge of the rectangle. A section is contiguous if each square in the section is connected to each other square in the section via a path of horizontally or vertically adjacent squares that are all within the section.
Constraints
- a will be between 1 and 6, inclusive.
- b will be between 2 and 6, inclusive.
Examples
0)
1 3 Returns: 2
There are two different ways to split up this rectangle, where '#' represents one section, and '.' the other: ##. #..
1)
3 2 Returns: 15
Here are the 15 ways: #. .# .. .. #. .# .. .. .. .. .. .. #. .# #. .# .. .. #. .# .. .. #. .# ## .. ## ## ## ## #. .. .. #. .# #. .# #. .. ## ## ## .. .. #.
2)
1 2 Returns: 1
3)
1 3 Returns: 2
4)
1 4 Returns: 3
Submissions are judged against all 32 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RectangleDivision with a public method int count(int a, int b) · 32 test cases · 2 s / 256 MB per case