PlusCastle
SRM 772 · 2019-12-10 · by misof
Problem Statement
Given count plus signs ('+'), arrange them in a way that maximizes the number of closed figures. Assume that horizontally or vertically adjacent plus signs touch each other.
For example, the following arrangement of 8 plus signs contains three closed figures (squares, each formed by parts of four + signs):
++++ ++++
The following arrangement contains 10 plus signs but only one closed figure (a 2x3 rectangle with some short line segments on the inside):
++++ + + ++++
And the following arrangement of 6 plus signs contains no closed figures at all:
+ + + + ++
Compute and return the largest number of closed figures that can be produced using exactly count plus signs.
Constraints
- count will be between 1 and 1,000,000,000, inclusive
546 Returns: 500
992 Returns: 930
555 Returns: 508
5 Returns: 1
980 Returns: 918
9 Returns: 4
The following arrangement maximises the number of closed figures: +++ +++ +++
6 Returns: 2
The following arrangement maximises the number of closed figures: +++ +++
Submissions are judged against all 119 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PlusCastle with a public method int maximiseClosedFigures(int k) · 119 test cases · 2 s / 256 MB per case