Statistics

Problem Statement for "PlanarGraphShop"

Problem Statement

In the Kocurkovo village there is a shop that sells simple planar graphs. (See Notes for a definition.)

The cost of any graph with X vertices and Y edges is (X^3 + Y^2) gold coins.

Monika has N gold coins, and she wants to spend all of them on simple planar graphs.

Write a method that gets the value N and computes the minimum number of simple planar graphs Monika has to buy in order to spend exactly N gold coins. She is allowed to buy multiple graphs of the same type.

Definition

Class:
PlanarGraphShop
Method:
bestCount
Parameters:
int
Returns:
int
Method signature:
int bestCount(int N)
(be sure your method is public)

Notes

  • A simple graph is an ordered pair (V,E) where V is a finite non-empty set of objects called vertices, and E is a finite set of edges. Each edge is a two-element subset of V. (You can find drawings of several graphs in Example #3.)
  • Note that a simple graph does not contain any loops (edges that connect a vertex to itself) and any duplicate edges. In other words, each edge connects two different vertices, and each pair of vertices is connected by at most one edge.
  • A graph is called planar if it has a drawing in the plane such that no two edges intersect.
  • Note that a simple planar graph does not have to be connected.

Constraints

  • N will be between 1 and 50,000, inclusive.

Examples

  1. 36

    Returns: 1

    For 36 gold coins she can buy a triangle: a simple planar graph with 3 vertices and 3 edges.

  2. 7

    Returns: 7

    The only simple planar graph that costs 7 gold coins or less is the graph that consists of a single vertex (and no edges). This graph costs 1^3 + 0^2 = 1, so Monika has to buy 7 of them.

  3. 72

    Returns: 2

    She can buy 2 triangles for 36 gold coins each. No simple planar graph costs exactly 72 gold coins, hence the optimal answer in this case is 2.

  4. 46

    Returns: 3

    All the graphs Monika can afford are shown in the following picture: One optimal solution is to buy graphs worth 1 + 9 + 36 gold coins.

  5. 50000

    Returns: 2

  6. 1099

    Returns: 2

  7. 1

    Returns: 1

  8. 8

    Returns: 1

  9. 49905

    Returns: 1

  10. 46656

    Returns: 1

  11. 46657

    Returns: 1

  12. 15

    Returns: 7

  13. 23

    Returns: 7

  14. 34

    Returns: 4

  15. 42

    Returns: 4

  16. 50

    Returns: 4

  17. 51

    Returns: 4

  18. 61

    Returns: 4

  19. 79

    Returns: 4

  20. 114

    Returns: 4

  21. 18735

    Returns: 3

  22. 13099

    Returns: 3

  23. 6692

    Returns: 3

  24. 5711

    Returns: 3

  25. 4691

    Returns: 3

  26. 3703

    Returns: 3

  27. 2739

    Returns: 3

  28. 1995

    Returns: 3

  29. 996

    Returns: 3

  30. 49998

    Returns: 2

  31. 49993

    Returns: 2

  32. 49930

    Returns: 2

  33. 2

    Returns: 2

  34. 7

    Returns: 7

  35. 10

    Returns: 2

  36. 12

    Returns: 4

  37. 17

    Returns: 2

  38. 36

    Returns: 1

  39. 43

    Returns: 3

  40. 52

    Returns: 3

  41. 100

    Returns: 1

  42. 113

    Returns: 3

  43. 128

    Returns: 2

  44. 206

    Returns: 1

  45. 225

    Returns: 1

  46. 246

    Returns: 3

  47. 360

    Returns: 1

  48. 385

    Returns: 3

  49. 412

    Returns: 2

  50. 568

    Returns: 1

  51. 599

    Returns: 2

  52. 632

    Returns: 2

  53. 836

    Returns: 1

  54. 873

    Returns: 1

  55. 912

    Returns: 2

  56. 1170

    Returns: 1

  57. 1213

    Returns: 3

  58. 1258

    Returns: 2

  59. 1576

    Returns: 1

  60. 1625

    Returns: 2

  61. 1676

    Returns: 2

  62. 2060

    Returns: 1

  63. 2115

    Returns: 2

  64. 2172

    Returns: 2

  65. 2628

    Returns: 1

  66. 9668

    Returns: 2

  67. 10916

    Returns: 1

  68. 11025

    Returns: 1

  69. 11136

    Returns: 2

  70. 12510

    Returns: 1

  71. 12625

    Returns: 2

  72. 12742

    Returns: 2

  73. 14248

    Returns: 1

  74. 14369

    Returns: 2

  75. 14492

    Returns: 2

  76. 16136

    Returns: 1

  77. 16263

    Returns: 2

  78. 16392

    Returns: 2

  79. 18180

    Returns: 1

  80. 18313

    Returns: 2

  81. 18448

    Returns: 2

  82. 20386

    Returns: 1

  83. 20525

    Returns: 2

  84. 31278

    Returns: 2

  85. 34056

    Returns: 1

  86. 34225

    Returns: 2

  87. 34396

    Returns: 2

  88. 37360

    Returns: 1

  89. 37535

    Returns: 2

  90. 37712

    Returns: 2

  91. 40868

    Returns: 1

  92. 41049

    Returns: 2

  93. 41232

    Returns: 2

  94. 44586

    Returns: 1

  95. 44773

    Returns: 2

  96. 44962

    Returns: 2

  97. 48520

    Returns: 1

  98. 48713

    Returns: 2

  99. 48908

    Returns: 2

  100. 18735

    Returns: 3

  101. 13099

    Returns: 3

  102. 6692

    Returns: 3

  103. 6615

    Returns: 3

  104. 6016

    Returns: 3

  105. 114

    Returns: 4

  106. 79

    Returns: 4

  107. 61

    Returns: 4

  108. 23

    Returns: 7

  109. 9912

    Returns: 2

  110. 9

    Returns: 1

  111. 231

    Returns: 3

  112. 453

    Returns: 3

  113. 35483

    Returns: 2

  114. 441

    Returns: 2

  115. 4356

    Returns: 2

  116. 45987

    Returns: 2

  117. 189

    Returns: 1

  118. 32413

    Returns: 2

  119. 49931

    Returns: 1

  120. 64

    Returns: 1

  121. 164

    Returns: 2

  122. 4896

    Returns: 1

  123. 49989

    Returns: 2

  124. 34744

    Returns: 2

  125. 487

    Returns: 1

  126. 40

    Returns: 2

  127. 30600

    Returns: 1

  128. 316

    Returns: 1

  129. 3025

    Returns: 2

  130. 32768

    Returns: 1

  131. 185

    Returns: 3

  132. 19

    Returns: 3

  133. 49913

    Returns: 2

  134. 12345

    Returns: 2

  135. 108

    Returns: 2

  136. 343

    Returns: 1

  137. 4196

    Returns: 1

  138. 71

    Returns: 3

  139. 174

    Returns: 1

  140. 1400

    Returns: 1

  141. 1036

    Returns: 1

  142. 344

    Returns: 1

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: