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
546
Returns: 500
992
Returns: 930
555
Returns: 508
5
Returns: 1
980
Returns: 918
980
Returns: 918
125
Returns: 103
528
Returns: 483
729
Returns: 676
981
Returns: 919
956
Returns: 895
13
Returns: 6
536
Returns: 490
250
Returns: 219
677
Returns: 625
851
Returns: 793
601
Returns: 552
419
Returns: 379
476
Returns: 433
471
Returns: 428
176111
Returns: 175272
581335
Returns: 579811
702358
Returns: 700682
702007
Returns: 700332
825252
Returns: 823436
952303
Returns: 950352
4136
Returns: 4008
219608
Returns: 218671
399517
Returns: 398253
521776
Returns: 520332
428582
Returns: 427273
708713
Returns: 707030
593466
Returns: 591926
992061
Returns: 990069
526748
Returns: 525297
203142
Returns: 202241
133712
Returns: 132981
124299
Returns: 123594
882825
Returns: 880946
675357
Returns: 673714
549222
Returns: 547740
581924
Returns: 580399
43423
Returns: 43007
613556
Returns: 611990
245819
Returns: 244828
401316
Returns: 400050
671109
Returns: 669471
894433
Returns: 892542
324990
Returns: 323850
988223
Returns: 986235
963733
Returns: 961770
113040
Returns: 112368
937685
Returns: 935749
699705
Returns: 698033
364254
Returns: 363047
340354
Returns: 339188
196695
Returns: 195808
824364
Returns: 822549
81699
Returns: 81128
817928
Returns: 816120
177002140
Returns: 176975532
180608681
Returns: 180581803
871223508
Returns: 871164476
340434466
Returns: 340397565
858265902
Returns: 858207310
610026110
Returns: 609976713
409461583
Returns: 409421113
891436319
Returns: 891376606
660218991
Returns: 660167602
549786700
Returns: 549739805
999909754
Returns: 999846512
606379991
Returns: 606330742
551388513
Returns: 551341550
252587979
Returns: 252556193
213483450
Returns: 213454228
638270295
Returns: 638219767
181104029
Returns: 181077115
955745807
Returns: 955683977
820566647
Returns: 820509356
878105811
Returns: 878046546
231949657
Returns: 231919198
945624090
Returns: 945562588
576376399
Returns: 576328384
145626178
Returns: 145602043
333453630
Returns: 333417109
973841188
Returns: 973778776
888104013
Returns: 888044411
421826453
Returns: 421785377
644740114
Returns: 644689331
595299005
Returns: 595250208
359189466
Returns: 359151562
350442765
Returns: 350405325
264892429
Returns: 264859878
139282275
Returns: 139258672
501570573
Returns: 501525782
815198144
Returns: 815141041
728587480
Returns: 728533496
287783887
Returns: 287749959
549772992
Returns: 549726098
261796623
Returns: 261764263
9
Returns: 4
The following arrangement maximises the number of closed figures: +++ +++ +++
6
Returns: 2
The following arrangement maximises the number of closed figures: +++ +++
1000000000
Returns: 999936755
898680485
Returns: 898620529
11
Returns: 5
36
Returns: 25
7
Returns: 2
1
Returns: 0
15
Returns: 8
3
Returns: 0
14
Returns: 7
49
Returns: 36
60
Returns: 45
18
Returns: 10
12
Returns: 6
33
Returns: 22
20
Returns: 12
9890
Returns: 9692
21
Returns: 12