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:
Helga Hufflepuff's Cup
Yuhao and a Parenthesis
Tanya and Password
Ice Cream
Optimize!
Gambling Nim
Point location in O(log n)
Prince's Problem
SMSC
Jordan Smiley
Falling Blocks
Josephus Problem
Happy Cactus
Number of Ways
Suns and Rays
Rectangle Puzzle
Captains Mode
Save the problem
Hate "A"
New Year and Ascent Sequence
Au Pont Rouge
Suffix Automaton
Xenia and Hamming
Let Them Slide
Vanya and Exams
Range Minimum Query
Optimal Subsequences (Hard Version)
Maximum Waterfall
And Yet Another Bracket Sequence
Party
Summer Homework
Perfect Security