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:
Vladislav and a Great Legend
Bookshelves
Robots on a Grid
Check whether a graph is bipartite
Games on arbitrary graphs
Playing with Permutations
Kuroni the Private Tutor
Remainders Game
Point location in O(log n)
Nikita and stack
New Year and the Tricolore Recreation
Magic Odd Square
Two-gram
Heavy-light decomposition
Finding the largest zero submatrix
Kay and Eternity
Orac and Medians
Independent Set
Place Your Ad Here
Integration by Simpson's formula
Producing Snow
Teams
Tourism
Cursor Distance
Dome
PolandBall and Many Other Balls
Ehab's REAL Number Theory Problem
Finding articulation points in a graph in $O(N+M)$
Kate and imperfection
Startup Funding
PolandBall and Game
Felicity is Coming!