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
36
Returns: 1
For 36 gold coins she can buy a triangle: a simple planar graph with 3 vertices and 3 edges.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.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.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.
Back to all problems