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:
Bathroom terminal
Kuroni and the Punishment
Bombs
K-th order statistic in O(N)
Bulbo
Orchestra
Treasure
Bits And Pieces
Travel Card
Desk Disorder
Om Nom and Candies
Bribes
Kay and Eternity
Memory for Arrays
Good Substrings
Run for beer
Table Compression
Bacterial Melee
Tree and XOR
New Year and the Factorisation Collaboration
Convex hull trick and Li Chao tree
Special Task
Security
JYPnation
Practice
A + B Strikes Back
Gotta Catch Em' All!
Circle-Line Intersection
Circle-Circle Intersection
4-point polyline
Pudding Monsters
Tổng hợp các bài toán duyệt với gợi ý lời giải