Vanya got n cubes. He decided to build a pyramid from them. Vanya wants to build the pyramid as follows: the top level of the pyramid must consist of 1 cube, the second level must consist of 1 + 2 = 3 cubes, the third level must have 1 + 2 + 3 = 6 cubes, and so on. Thus, the i-th level of the pyramid must have 1 + 2 + … + (i - 1) + i cubes.
Vanya wants to know what is the maximum height of the pyramid that he can make using the given cubes.
Input
The first line contains integer n (1 ≤ n ≤ 104) — the number of cubes given to Vanya.
Output
Print the maximum possible height of the pyramid in the single line.
Examples
input
1
output
1
input
25
output
4
Note
Illustration to the second sample:
Solution:
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> using namespace std; int main() { int n; scanf("%d", &n); int x = 1; int cur = 1; while (n >= cur) { n -= cur; x++; cur += x; } printf("%d\n", x - 1); return 0; }
Related posts:
Finding area of simple polygon in $O(N)$
Challenges in school №41
Increase Sequence
New Year and Fireworks
Ehab and Path-etic MEXs
Unusual Graph
Ant colony
A Trivial Problem
Pillars
Not Wool Sequences
Koala and Notebook
Sherlock's bet to Moriarty
Subarray Cuts
Palindrome
Frets On Fire
Number Transformation
Auto completion
Flawed Flow
Can Bash Save the Day?
Helping People
Serega and Fun
Sherlock and his girlfriend
Two Regular Polygons
Professor GukiZ and Two Arrays
PolandBall and Polygon
Hot is Cold
Berland Federalization
Mergesort Strikes Back
Merging Two Decks
Level Statistics
Spyke Talks
Resource Distribution