UVa 11401 Triangle Counting:组合计数

11401 - Triangle Counting

Time limit: 1.000 seconds

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=469&page=show_problem&problem=2396

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 with n<3. This case should not be processed.

Output

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45374.htm

For each test case, print the number of distinct triangles you can make.

Sample Input    Output for Sample Input

首先算出当最大边为x的符合题意的个数有多少，再用递推式累加即可。（因为题目要算的是边长不超过n的个数）

完整代码：

/*0.029s*/

#include<cstdio>  

long long f[1000010];  

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), n >= 3)
        printf("%lld\n", f[n]);
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索length
， have
Counting
triangle、little triangle、bermuda triangle、triangle社、triangle 韩剧，以便于您获取更多的相关知识。