Statistics

Problem Statement for "LandSplitter"

Problem Statement

A lord owned a piece of land with area N. He wanted to give parts of this land as rewards to his subjects, so he decided that he will split the piece of land into one or more pieces in such a way that the size of each piece will be between A and B, inclusive. But splitting pieces of land is regulated by the king of this country, as follows:

  • Each piece of land must always have a positive integer area.
  • For all X, Y: The owner of a piece of land of size X+Y may split it into two pieces of size X and Y, but if they do, they have to pay the king X*Y in taxes.
  • For all X, Y, Z: The owner of a piece of land of size X+Y+Z may split it into three pieces of size X, Y, and Z, but if they do, they have to pay the king X*Y + Y*Z + Z*X in taxes.

Return -1 if the lord cannot reach his goal. Otherwise, return the smallest total amount of taxes with which the lord can reach his goal.

Definition

Class:
LandSplitter
Method:
cheapest
Parameters:
int, int, int
Returns:
long
Method signature:
long cheapest(int N, int A, int B)
(be sure your method is public)

Notes

  • For the chosen constraints the answer always fits into a 64-bit signed integer.

Constraints

  • 1 <= A <= B <= N <= 100,000,000.

Examples

  1. 12

    3

    3

    Returns: 54

    One optimal solution is to split the land into two halves (cost 36) and then separately each half into halves (cost 9 twice).

  2. 10

    3

    4

    Returns: 33

    One optimal solution is to directly split the land into pieces of size 3, 3, and 4.

  3. 47

    1

    47

    Returns: 0

    Clearly, the optimal solution is to do nothing.

  4. 70

    40

    50

    Returns: -1

    A land of size 70 cannot be split into pieces of size between 40 and 50, inclusive.

  5. 47

    4

    7

    Returns: 945

  6. 100000000

    1

    99999999

    Returns: 99999999

  7. 99999987

    5

    7

    Returns: 4999998350000140

  8. 99999987

    10000000

    11200000

    Returns: 4444158835200000

  9. 12

    2

    2

    Returns: 60

  10. 18

    10

    15

    Returns: -1

  11. 11

    5

    5

    Returns: -1

  12. 13

    5

    7

    Returns: 42

  13. 2

    1

    2

    Returns: 0

  14. 4

    1

    1

    Returns: 6

  15. 16

    1

    1

    Returns: 120

  16. 19

    4

    14

    Returns: 70

  17. 8

    4

    6

    Returns: 16

  18. 8

    1

    1

    Returns: 28

  19. 12

    6

    10

    Returns: 36

  20. 18

    2

    7

    Returns: 105

  21. 2

    1

    1

    Returns: 1

  22. 4

    3

    3

    Returns: -1

  23. 13

    9

    9

    Returns: -1

  24. 9

    1

    2

    Returns: 32

  25. 11

    4

    4

    Returns: -1

  26. 4

    3

    4

    Returns: 0

  27. 10

    3

    4

    Returns: 33

  28. 12

    1

    9

    Returns: 27

  29. 16

    10

    10

    Returns: -1

  30. 13

    5

    5

    Returns: -1

  31. 8

    1

    2

    Returns: 24

  32. 13

    5

    8

    Returns: 40

  33. 20

    5

    18

    Returns: 75

  34. 15

    1

    1

    Returns: 105

  35. 18

    1

    3

    Returns: 135

  36. 9

    9

    9

    Returns: 0

  37. 16

    6

    14

    Returns: 60

  38. 2

    2

    2

    Returns: 0

  39. 11

    1

    1

    Returns: 55

  40. 7

    2

    3

    Returns: 16

  41. 6

    2

    2

    Returns: 12

  42. 7

    1

    2

    Returns: 18

  43. 5

    3

    5

    Returns: 0

  44. 17

    2

    13

    Returns: 52

  45. 9

    1

    8

    Returns: 8

  46. 4

    1

    4

    Returns: 0

  47. 12

    1

    1

    Returns: 66

  48. 2

    1

    1

    Returns: 1

  49. 17

    7

    16

    Returns: 70

  50. 16

    10

    15

    Returns: -1

  51. 19

    1

    1

    Returns: 171

  52. 6

    2

    2

    Returns: 12

  53. 2

    1

    1

    Returns: 1

  54. 13

    1

    2

    Returns: 72

  55. 3

    1

    2

    Returns: 2

  56. 18

    4

    10

    Returns: 80

  57. 20

    5

    18

    Returns: 75

  58. 18

    2

    9

    Returns: 81

  59. 75559089

    144751

    199978

    Returns: 2847035615429382

  60. 15380714

    3288

    18321

    Returns: 118142328474186

  61. 75741865

    670723

    33864616

    Returns: 1689501696215312

  62. 8527695

    31253

    112132

    Returns: 35885048419226

  63. 2399513

    1013

    10288

    Returns: 2866497713968

  64. 67430252

    3404

    3414

    Returns: 2273304344186952

  65. 22403306

    313621

    330744

    Returns: 247262880616435

  66. 90051562

    268

    31741

    Returns: 4053212780472011

  67. 75188601

    3

    102

    Returns: 2826659025550602

  68. 72779968

    4

    57917

    Returns: 2646354665298892

  69. 69909066

    225958

    8424299

    Returns: 2156601707267436

  70. 77639794

    23651506

    23652438

    Returns: -1

  71. 98296090

    12

    1240362

    Returns: 4770242712282780

  72. 54368856

    9

    1769

    Returns: 1477938162399831

  73. 83540525

    2253

    15540079

    Returns: 2868720961113760

  74. 46946839

    6290

    298042

    Returns: 1095017871135474

  75. 34136323

    123

    223

    Returns: 582640467785546

  76. 88761318

    31556331

    31557297

    Returns: -1

  77. 42607698

    31

    2326908

    Returns: 858715836360768

  78. 82594

    30732

    30732

    Returns: -1

  79. 82417636

    12

    417

    Returns: 3396316177851618

  80. 16622634

    2042

    2100

    Returns: 138138527769944

  81. 57176331

    1071

    1265

    Returns: 1634530249499189

  82. 81723760

    1008547

    4696684

    Returns: 3150118881035312

  83. 82809844

    3678464

    3856589

    Returns: 3272800289020185

  84. 5744012

    606006

    606048

    Returns: -1

  85. 65089467

    246

    9424

    Returns: 2118012663296352

  86. 23610327

    1

    941509

    Returns: 267640645034750

  87. 99756842

    1

    7

    Returns: 4975713413757541

  88. 67018618

    1831233

    17855550

    Returns: 1677038859074700

  89. 98062724

    9

    22

    Returns: 4808147840460184

  90. 56410436

    707611

    717510

    Returns: 1570927668183144

  91. 89270734

    19455

    83404

    Returns: 3980909988073760

  92. 53083556

    11413

    119860

    Returns: 1405751421695920

  93. 42464563

    31

    4737

    Returns: 901518980840514

  94. 44702628

    504

    1268950

    Returns: 970941508446000

  95. 12443256

    4762

    6930

    Returns: 77374201820408

  96. 80738914

    99310

    99490

    Returns: 3255372091770660

  97. 95733129

    80443

    27144577

    Returns: 3374937511720725

  98. 75451238

    11362665

    11362667

    Returns: -1

  99. 65534963

    7979

    6226549

    Returns: 1948221398609815

  100. 950049

    13

    471651

    Returns: 228819124395

  101. 8629152

    174

    211

    Returns: 37230221754087

  102. 10733635

    4

    24

    Returns: 57605331353040

  103. 16904725

    2546

    471145

    Returns: 138914288158625

  104. 55655631

    3552225

    3552960

    Returns: -1

  105. 12093046

    8

    1707414

    Returns: 62907500414220

  106. 27088153

    1210

    167794

    Returns: 364614865109726

  107. 42859587

    111693

    31282657

    Returns: 362157130303010

  108. 69970926

    1969481

    2090787

    Returns: 2375918066908845

  109. 58524406

    16620516

    20450391

    Returns: 1139038495326849

  110. 3043421

    3

    107

    Returns: 4631042869467

  111. 13570992

    13

    20460

    Returns: 91947124114560

  112. 58673998

    1407

    9380076

    Returns: 1454497021701792

  113. 89775744

    16357587

    16373458

    Returns: -1

  114. 92980645

    178

    81378

    Returns: 4318917690921768

  115. 84201715

    1314

    1314

    Returns: -1

  116. 90649713

    4

    53

    Returns: 4108682831273865

  117. 81152275

    1061792

    1062348

    Returns: -1

  118. 34384141

    187448

    190282

    Returns: 587868567873120

  119. 49576690

    121

    2715

    Returns: 1228856796081750

  120. 82704362

    838425

    838427

    Returns: -1

  121. 56609827

    13885

    13898

    Returns: 1601942948561222

  122. 66810858

    16622762

    16623040

    Returns: -1

  123. 30833175

    2

    464

    Returns: 475335187010400

  124. 52763045

    2411

    2527

    Returns: 1391902793591509

  125. 46325396

    18604

    14094736

    Returns: 766863182688192

  126. 8785215

    5

    50257

    Returns: 38369439648345

  127. 27477931

    45708

    45943

    Returns: 376888094911890

  128. 39824230

    536727

    536727

    Returns: -1

  129. 33702903

    228765

    415672

    Returns: 560982624495299

  130. 63217939

    4410

    4515

    Returns: 1998111193613535

  131. 90329820

    1729

    1920035

    Returns: 3993100744772100

  132. 1004191

    561

    568

    Returns: 503914601258

  133. 81734989

    2

    65

    Returns: 3340301557028410

  134. 51465254

    75

    32347809

    Returns: 618407459428005

  135. 37212616

    111131

    3866834

    Returns: 622196845739676

  136. 5074755

    850593

    850598

    Returns: -1

  137. 6983546

    29712

    1017206

    Returns: 20893360379700

  138. 97780733

    9897411

    23866365

    Returns: 3744563408793582

  139. 33985165

    14

    14324

    Returns: 577252342846192

  140. 50663302

    1

    50

    Returns: 1283383818189100

  141. 77190179

    23

    2899912

    Returns: 2868232033152304

  142. 11583464

    15012

    15012

    Returns: -1

  143. 94903724

    28

    10309

    Returns: 4502869237649965

  144. 72328674

    331

    2013762

    Returns: 2543046175039860

  145. 10077471

    4

    5

    Returns: 50777685684251

  146. 18384429

    830593

    830602

    Returns: -1

  147. 76497187

    259016

    1221940

    Returns: 2879351035221560

  148. 82203886

    41

    274483

    Returns: 3367467062628812

  149. 31034908

    1007

    1016

    Returns: 481566991975929

  150. 87294986

    848522

    911476

    Returns: 3770511749557684

  151. 54991659

    716682

    32583626

    Returns: 730134966667658

  152. 1717090

    59509

    75684

    Returns: 1409956881477

  153. 46101445

    915

    4198

    Returns: 1062574850200026

  154. 50528975

    30

    32

    Returns: 1276587848811968

  155. 52664484

    279942

    279950

    Returns: -1

  156. 49361225

    2715780

    4477807

    Returns: 1114075126421490

  157. 147100

    34

    468

    Returns: 10784807280

  158. 55340374

    24

    53990

    Returns: 1529784600484000

  159. 100000000

    3300

    3313

    Returns: 4999834354793271

  160. 100000000

    1

    1

    Returns: 4999999950000000

  161. 100000000

    1

    10

    Returns: 4999999500000000

  162. 3927

    541

    3427

    Returns: 1831826

  163. 6

    3

    4

    Returns: 9

  164. 100000000

    1

    1234

    Returns: 4999938300152532

  165. 100000000

    101

    997

    Returns: 4999950150043650

  166. 100000000

    1

    100000000

    Returns: 0

  167. 100000000

    43

    57

    Returns: 4999997150000055

  168. 12

    5

    6

    Returns: 36

  169. 10

    6

    10

    Returns: 0

  170. 100000000

    100000000

    100000000

    Returns: 0

  171. 297

    99

    100

    Returns: 29403

  172. 17348426

    720412

    8345653

    Returns: 81100731748501

  173. 100000000

    2

    5

    Returns: 4999999750000000

  174. 67376

    2151

    2230

    Returns: 2196525379

  175. 61927295

    3586081

    17261150

    Returns: 1419125188332750

  176. 397

    60

    78

    Returns: 65460

  177. 49445077

    7567700

    34843120

    Returns: 508777739985840

  178. 39

    5

    6

    Returns: 651

  179. 75088453

    6376664

    21601913

    Returns: 2066306815474353

  180. 100

    30

    45

    Returns: 3300

  181. 100000000

    1

    2

    Returns: 4999999900000000

  182. 5

    2

    2

    Returns: -1

  183. 13

    5

    6

    Returns: -1

  184. 4

    1

    3

    Returns: 3

  185. 101

    1

    100

    Returns: 100

  186. 76087748

    13882820

    74301434

    Returns: 863579818536960

  187. 96930886

    91692777

    94289383

    Returns: -1

  188. 15825826

    2792693

    11154407

    Returns: 52106908793533

  189. 100000000

    1

    30000000

    Returns: 3600000000000000

  190. 18

    3

    5

    Returns: 120

  191. 99981235

    2

    3

    Returns: 4998123526090762

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.
This problem was used for: