BiggestRectangleHard
SRM 318 · 2006-08-29 · by Andrew_Lazarev
Problem Statement
Little Josh has found several sticks of various lengths. He wants to form a rectangle with the biggest possible area, using these sticks as the perimeter. He is allowed to glue sticks together, but he is not allowed to break single sticks into multiple shorter sticks. Sticks may only be glued together at their endpoints, so a stick of length 2 and a stick of length 3 can only be glued together to form a stick of length 5.
For example, if Josh has sticks with lengths {1, 3, 3, 4, 5, 7}, he can create a 3 x 5 rectangle using the two sticks of length 3, the stick of length 5, and the sticks of lengths 1 and 4 glued together. This rectangle has an area of 15 square inches, which is the biggest area that can be achieved with these sticks.
You will be given a
Constraints
- lengths will contain between 4 and 16 elements, inclusive.
- Each element of lengths will be between 1 and 10, inclusive.
{1, 3, 3, 4, 5, 7}
Returns: 15
The example from the problem statement.
{9, 9, 5, 6, 2, 10}
Returns: -1
It is impossible to create a rectangle using these sticks.
{3, 4, 7, 8, 10, 2, 9}
Returns: 70
The best rectangle is 7x10.
{9, 2, 7, 9, 4, 9, 7, 10, 3}
Returns: 224
The best rectangle is 14x16.
{9, 9, 10, 7, 7, 8, 7, 5, 8, 6, 9, 7, 7, 10, 9, 6}
Returns: 961
The best rectangle is a square 31x31.
Submissions are judged against all 95 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BiggestRectangleHard with a public method int findArea(vector<int> lengths) · 95 test cases · 2 s / 256 MB per case