Description
Problem G
Triangle Counting
Input: Standard Input
Output: Standard Output
You are given n rods of length 1, 2…, n. You have to pick any 3 of them & build a triangle. How many distinct triangles can you make? Note that, two triangles will be considered different if they have at least 1 pair of arms with different length.
Input
The input for each case will have only a single positive integer n (3<=n<=1000000). The end of input will be indicated by a case withn<3. This case should not be processed.
Output
For each test case, print the number of distinct triangles you can make.
Sample Input Output for Sample Input
Problemsetter: Mohammad Mahmudur Rahman
设最大边为x的三角形有c(x)个,另外两条边分别为y和z,根据三角形不等式有y+z>x,所以z的取值范围x-y<z<x。当y等于1时,无解;y=2时,只有一个解,y=3时,有两个解,直到y=x-1时有x-2个解。根据等差数列求和,一共有(x-1)(x-2)/2个解。当然,这里面还包含了y=z的情况,而且每个三角形算了两遍。所以要统计y=z的情况。所以一共有1/2*((x-1)*(x-2)/2-(x-1)/2)种情况。
原题要求f(n)。根据加法原理f(n)=c(1)+c(2)+......+c(n).可以写成地推形式f(n)=f(n-1)+c(n)。
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 1000010;
long long counts[maxn];
int main()
{
counts[3] = 0;
for(long long x = 4; x <= 1000000; x++)
{
counts[x] = counts[x-1] + (((x-1)*(x-2))/2-(x-1)/2)/2;
}
int n;
while(cin>>n && n >= 3)
{
cout << counts[n] << endl;
}
return 0;
}