Codeforces Round #280 (Div. 2)-A. Vanya and Cubes_html/css_WEB-ITnose

Vanya and Cubes

time limit per test

memory limit per test

input

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最多可以构成多少层。

div+css3阶梯分页样式

div+css3阶梯分页样式

84

查看详情

分析；水题，直接找规律的题。看了一眼，感觉太水，就没敢暴力。。。瞬间想起了以前跟tourist学的一个方法，把个n的区间，都预处理成最高层数，然后查询就是O（1）的了。可惜了，边玩边水，硬是水了一个小时。。。最后看别人的代码，直接暴力也不超时。只能说，数据太弱了。

AC代码：

#include <cstdio>#include <algorithm>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<foo && sum+j<=10000 ; j++){            a[sum+j] = i-1;        }        sum += foo;    }    int n;    while(scanf("%d", &n)==1){        printf("%d\n", a[n]);    }    return 0;}

切记，下次不能在水题上浪费时间了。。。