Statistics

Problem Statement for "CubeTower"

Problem Statement

Xenia and Yvona have a new toy: a collection of wooden cubes. Each cube has a positive integer side length. They have a large enough supply of cubes of all possible sizes.

Both girls have decided to use exactly N cubes, placed on top of each other, to build a tower that would have height exactly H.

Calculate and return the largest possible positive difference between the volumes of their two towers.

Definition

Class:
CubeTower
Method:
difference
Parameters:
int, int
Returns:
long
Method signature:
long difference(int H, int N)
(be sure your method is public)

Notes

  • No weird cube placements allowed. The bottom cube in the tower is placed on the ground (so that its bottom face is horizontal), and each of the following cubes is placed onto the previous one so that the top face of the previous one and the bottom face of the current one touch and overlap partially.
  • Watch out for integer overflow, the correct return value will sometimes overflow a 32-bit integer variable.
  • The smallest cube has side = 1. It is not allowed to use cubes with side = 0.

Constraints

  • H will be between 1 and 10^6, inclusive.
  • N will be between 1 and H, inclusive.

Examples

  1. 4

    2

    Returns: 12

    We want a tower of height 4 using exactly 2 cubes. There are three possible towers: start with a 3x3x3 cube and place a 1x1x1 cube on top of it start with a 2x2x2 cube and place another 2x2x2 cube on top of it start with a 1x1x1 cube and place a 3x3x3 cube on top of it The tower of the second kind has volume 8+8 = 16, the other two types of tower have volume 27+1 = 28. If one of the girls builds a tower of the second kind and the other girl a different tower, the difference between their volumes will be 28 - 16 = 12.

  2. 17

    16

    Returns: 0

    There are multiple different towers the girls may build but they all share the same total volume. (Each of those towers consists of fifteen 1x1x1 cubes and one 2x2x2 cube.)

  3. 5

    3

    Returns: 12

  4. 1000000

    1

    Returns: 0

  5. 1000000

    1000000

    Returns: 0

  6. 1000000

    123456

    Returns: 673476816437812224

  7. 1000000

    200000

    Returns: 512001919977600000

  8. 1000000

    7

    Returns: 979573836842326320

  9. 1000000

    10

    Returns: 989973000242999280

  10. 999999

    2

    Returns: 749994750010499994

  11. 2304

    453

    Returns: 6352122486

  12. 4431

    8

    Returns: 85226204406

  13. 502

    188

    Returns: 31252164

  14. 112601

    24315

    Returns: 688161350588256

  15. 3

    3

    Returns: 0

  16. 1069

    108

    Returns: 890172216

  17. 11206

    62

    Returns: 1383965793600

  18. 80

    10

    Returns: 352800

  19. 442527

    116963

    Returns: 34507470793305480

  20. 12

    6

    Returns: 300

  21. 1

    1

    Returns: 0

  22. 296847

    1013

    Returns: 25890964760732820

  23. 80495

    218

    Returns: 517345194873684

  24. 1365

    268

    Returns: 1323717684

  25. 180692

    553

    Returns: 5845599295119726

  26. 503

    15

    Returns: 116364192

  27. 225958

    11548

    Returns: 9856918898043360

  28. 4

    1

    Returns: 0

  29. 15686

    616

    Returns: 3423142020540

  30. 638

    59

    Returns: 195037170

  31. 2042

    1071

    Returns: 918323250

  32. 922034

    712507

    Returns: 9198694647299262

  33. 4446

    43

    Returns: 85368997716

  34. 606006

    59704

    Returns: 163042473792348084

  35. 2

    1

    Returns: 0

  36. 7

    1

    Returns: 0

  37. 62594

    2549

    Returns: 216497143188690

  38. 118028

    9

    Returns: 1623568792737450

  39. 14941

    6778

    Returns: 544137841182

  40. 11413

    1837

    Returns: 878391738420

  41. 5

    1

    Returns: 0

  42. 770967

    229140

    Returns: 159068553865446672

  43. 13

    5

    Returns: 636

  44. 317660

    174

    Returns: 32000994352543116

  45. 5

    5

    Returns: 0

  46. 468600

    2546

    Returns: 101230515094913280

  47. 13023

    2417

    Returns: 1193376733476

  48. 1232

    2

    Returns: 1397919600

  49. 166585

    1210

    Returns: 4522901676715470

  50. 1902

    1

    Returns: 0

  51. 342292

    3

    Returns: 35647506771898464

  52. 945022

    15

    Returns: 840179090820636462

  53. 810917

    327172

    Returns: 113201494583579844

  54. 100971

    1919

    Returns: 971857913814816

  55. 774665

    3

    Returns: 413223961827410292

  56. 826046

    58

    Returns: 563369906454464232

  57. 491577

    127793

    Returns: 48143134540435680

  58. 726412

    81201

    Returns: 268600803818007948

  59. 977767

    178

    Returns: 934235866820164080

  60. 657826

    1

    Returns: 0

  61. 341011

    21

    Returns: 39558759367737168

  62. 811705

    586

    Returns: 533646988199247390

  63. 49244

    2

    Returns: 89554198972212

  64. 268627

    2835

    Returns: 18777188296677084

  65. 582496

    111

    Returns: 197513829542767062

  66. 945884

    2595

    Returns: 839335565900470290

  67. 212230

    17515

    Returns: 7382524829643840

  68. 835134

    818

    Returns: 580754558725011816

  69. 442265

    14

    Returns: 86057308755405666

  70. 884564

    13885

    Returns: 660048279587883816

  71. 368938

    368932

    Returns: 300

  72. 580534

    552897

    Returns: 21111536064612

  73. 269933

    153732

    Returns: 1569064543221000

  74. 411478

    402900

    Returns: 631407828492

  75. 107433

    107432

    Returns: 0

  76. 988440

    955075

    Returns: 37146032438340

  77. 961968

    960070

    Returns: 6848162412

  78. 241222

    241004

    Returns: 10501932

  79. 463703

    463701

    Returns: 12

  80. 588195

    584701

    Returns: 42691487916

  81. 9

    3

    Returns: 264

  82. 1000000

    100

    Returns: 999603029402029800

  83. 1000000

    2

    Returns: 749997000003000000

  84. 1000000

    434567

    Returns: 180778075289638080

  85. 1000000

    5000

    Returns: 985077805077990000

  86. 999999

    4435

    Returns: 986753869600551360

  87. 10000

    50

    Returns: 984971912400

  88. 1000000

    3

    Returns: 888882888900222216

  89. 23

    7

    Returns: 4656

  90. 1000000

    79283

    Returns: 780512568656669214

  91. 1000000

    37478

    Returns: 891729938471193612

  92. 11

    8

    Returns: 42

  93. 1000000

    9

    Returns: 987630321179357520

  94. 1000000

    123

    Returns: 999567946428002364

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: