PyramidOfCubes
SRM 310 · 2006-07-06 · by misof
Problem Statement
Consider a N-level pyramid built of unit cubes. An example for N=3 can be seen in the image below.
Formally, a pyramid of size N has N levels, where the i-th level (counting from the top) contains an i by i grid of unit cubes.
You have K cubes. First, you select a suitable pyramid size as follows: If K is exactly the number of cubes necessary to build a pyramid of size N for some N, you pick that size. Otherwise, you pick the smallest pyramid size you can not build.
Now you start building the pyramid in a systematic bottom-up way. First you build the complete bottom level, then you build the level above that, etc. When building a level, also proceed in a systematic way, starting the next row only when the previous one is full.
For example, for 21 cubes you should get the following incomplete pyramid:
Given an
Notes
- The returned value must be accurate to within a relative or absolute value of 1E-9.
- The bottom sides of the cubes on the bottommost level are a part of the surface.
Constraints
- K will be between 1 and 1,000,000,000, inclusive.
14 Returns: 42.0
The first example from the problem statement.
21 Returns: 58.0
The second example from the problem statement.
1 Returns: 6.0
A single cube.
2 Returns: 10.0
Two cubes next to each other.
451234 Returns: 47498.0
Quite a lot of cubes.
Submissions are judged against all 77 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class PyramidOfCubes with a public method double surface(int K) · 77 test cases · 2 s / 256 MB per case