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:
Lowest Common Ancestor - Tarjan's off-line algorithm
Professor GukiZ and Two Arrays
Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor
Beautiful Sequence
Perfect Pair
Two Sets
Exploration plan
Fibonacci-ish
Modernization of Treeland
Petr and a Combination Lock
Grandfather Dovlet’s calculator
Koala and Notebook
The Holmes Children
Three Blocks Palindrome
Washer, Dryer, Folder
Quest
TOF
Intersection Point of Lines
Paint the Numbers
Optimal Point
Dijkstra on sparse graphs
Little Artem and 2-SAT
Neural Network country
Wrong Subtraction
Magic Odd Square
PolandBall and White-Red graph
Parity Game
Curious Array
K-th order statistic in O(N)
Strange Device
Counting labeled graphs
Tricky Interactor