Vanya and Cubes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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.
Sample test(s)
input
output
input
25
output
Note
Illustration to the second sample:
题意：最高层有1个 cube, 第二层有1?+?2?=?3 个cubes, 第三层有1?+?2?+?3?=?6 个 cubes, 依次递增. 然而, 第i层必须有 1?+?2?+?...?+?(i?-?1)?+?i 个 cubes.给一个n，问n个cube最多可以构成多少层。
分析；水题，直接找规律的题。看了一眼，感觉太水，就没敢暴力。。。瞬间想起了以前跟tourist学的一个方法，把个n的区间，都预处理成最高层数，然后查询就是O（1）的了。可惜了，边玩边水，硬是水了一个小时。。。最后看别人的代码，直接暴力也不超时。只能说，数据太弱了。
AC代码：
#include#include using namespace std;int a[10005];int main(){// freopen("in.txt", "r", stdin); int foo = 0; int sum = 0; for(int i=1; ; i++){ int t = foo; if(sum > 10000) break; foo += i; for(int j=0; j
切记，下次不能在水题上浪费时间了。。。