[UVa 11401]三角形计数

Grade Open Time Friday, 19 September 2014, 10:07 am
Discount 0.8 Time Discount Friday, 26 September 2014, 10:07 am
Allow late Yes Close Time Friday, 26 September 2014, 10:07 am
Input file TricountUVa.in Output file TricountUVa.out

【题目描述】

有多少种方法可以从1,2,3...,n中选3个不同的整数。使得以它们为三边长可以组成三角形?

比如n=5时有3种方法(2,3,4),(2,3,5),(3,4,5).n=8时有22种方法。

       


【输入格式】

输入包含多组测试数据,每组测试数据为一行整数n(3≤n≤1 000 000)。输入用n<3的标志结束。

【输出格式】

对于每组数据,输出其方案数(每组占一行)

【样例输入】

5
8
1

【样例输出】

3
22

【提示】

数据组数不会超过20组。

对于25%的数据:(3≤n≤100)

对于50%的数据:(3≤n≤1 000)

对于100%的数据:(3≤n≤1 000 000)

【来源】

UVa Triangle Counting,UVa 11401

刘汝佳,《算法竞赛入门经典训练指南》表2.2