PlusCastle | Topcoder Archive

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.

Definition

Class:: PlusCastle
Method:: maximiseClosedFigures
Parameters:: int
Returns:: int
Method signature:: int maximiseClosedFigures(int k)
(be sure your method is public)

Constraints

count will be between 1 and 1,000,000,000, inclusive

Examples

```
9
```
```
Returns: 4
```
The following arrangement maximises the number of closed figures: +++ +++ +++
```
6
```
```
Returns: 2
```
The following arrangement maximises the number of closed figures: +++ +++
```
898680485
```
```
Returns: 898620529
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.