Given a certain number of blocks N, your program must return the height of the tallest possible 2D pyramid that can be created, followed by the number of unused blocks remaining.
For example, a pyramid of height 3 contains 6 blocks: 3 for the first level, 2 for the second level and 1 for the last level.
INPUT:
Line 1: An integer N, the number of blocks to be used for the pyramid.
OUTPUT:
Line 1: Two integers H and R, where H is the greatest possible pyramid height, and R is the remaining unused blocks.
CONSTRAINTS:
0 ≤ N < 50000
EXAMPLE:
Input
10
Output
4 0
Solution
When going the pyramid from top to bottom, we need to sum \(1+2+3+4+...\). Since we have \(n\) blocks given, it follows:
\[\begin{array}{rrl} & n &\geq \sum\limits_{i=1}^h i\\ \Leftrightarrow & n &\geq \frac{1}{2}h(h+1)\\ \Leftrightarrow & 2n &\geq h^2+h\\ \Leftrightarrow & 2n+\frac{1}{4} &\geq (h+\frac{1}{2})^2\\ \Leftrightarrow & \sqrt{2n+\frac{1}{4}} &\geq h+\frac{1}{2}\\ \Leftrightarrow & \sqrt{2n+\frac{1}{4}}-\frac{1}{2} &\geq h\\ \Leftrightarrow & \frac{1}{2}\left(\sqrt{8n+1}-1\right) &\geq h\\ \Rightarrow & h &= \left\lceil\frac{\sqrt{8n+1}-1}{2}\right\rceil \end{array}\]
That was the first term. Since \(n = r + \sum\limits_{i=1}^h i\) follows, that \(r= n - \frac{1}{2}h(h+1)\). We now have all pieces together and can implement the thing. In Ruby this can look like:
N=gets
H=ceil((sqrt(8*N+1)-1)/2)
R=N-H*(H+1)/2
p [H,R].join(" ") It's quite short already. I think some bytes can be stripped off by simply looping down the pyramid. But I prefer this \(O(1)\) solution (seeing sqrt as constant).