Captain Brown Beard keeps his pirate ship stocked with a healthy supply of cannon balls. Because he is very tidy, he insists that all of the cannon balls be stacked into perfect tetrahedron shapes. Such a pyramid is constructed by arranging cannon balls into an equilateral triangle with side length n. Then, on top of that is stacked an equilateral triangle of side length n-1, and so on, until there is a single cannon ball placed on the top (this single cannon ball is a triangle of side length 1). For example, a stack of size 3 will have three layers that look like this (from top to bottom):
X
X
X X
X
X X
X X X
So, each triangle will contain 1, 3, 6, 10, etc. cannon balls. Thus, any complete stack will have 1, 4, 10, 20, etc. cannon balls.
You are given an int n, the number of cannon balls loaded on the ship. You are to return an int indicating the least possible number of stacks into which the cannon balls can be piled.
|