「CF492A」Vanya and Cubes
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
|
1 |
1 |
output
|
1 |
1 |
input
|
1 |
25 |
output
|
1 |
4 |
Note
Illustration to the second sample:
题解
模拟递推一下即可
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<map> #include<ctime> #include<vector> #include<set> #include<cmath> #include<algorithm> #define inf 1000000000 #define ll long long #define pa pair<int,int> using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,K,tot; int a[1005]; int main() { n=read(); for(int i=1;i<=1000;i++)a[i]=a[i-1]+i; for(int i=1;i<=1000;i++) if(tot+a[i]<=n)tot+=a[i]; else {printf("%d",i-1);break;} return 0; } |
Subscribe
计数器 9793305
OI 课件=>
OI 课件=>