Problem G
Triangle Counting
Input: StandardInput
Output: StandardOutput
You are given n rods of length 1, 2…, n. You have topick any 3 of them & build a triangle. How many distinct triangles can youmake? Note that, two triangles will be considered different if they have atleast 1 pair of arms with different
length.
Input
The input for each case will haveonly a single positive integer n
(3<=n<=1000000). The end of inputwill be indicated by a case with n<3. This case should not beprocessed.
Output
For each test case, print thenumber of distinct triangles you can make.
Sample Input output
5 8 0 |
3 22 |
思路:列出不等式进行优化!
#include <iostream> #include <algorithm> #include <cstdio> using namespace std; //11401 Triangle Counting Accepted C++ 0.044 2013-04-22 const int maxn = 1000010; long long f[maxn]; int main() { f[3] = 0; for(long long x = 4; x <= 1000000; x++) { f[x] = f[x-1] + (((x-1)*(x-2))/2-(x-1)/2)/2; } int n; while(scanf("%d",&n)==1) { if(n<3) break; cout << f[n] << endl; } return 0; }