UVA-11401 - Triangle Counting

• UVa Online Judge 解題結果請於 Submit 後，參閱 uHunt。
• 如果你有任何建議與指教，歡迎於下方留言一起討論喔！
• 本題選為「20161220 大學程式能力檢定 CPE」題目。
• 相同題目：NCTU-10920

題意概要

題目給定 $n$ 個長度不同的桿子，其長度分別為 $1$，$2$，…，$n$，從中選出三個不同的桿子以組成一個三角形，請問共有幾種組合方式？

• 分析：本題為動態規劃 (Dynamic Programming; DP) 的簡單題型。簡單來說，如果要討論使用長度為 $1$ ~ $N$ 的邊，則是使用長度為 $1$ ~ $N - 1$ 的邊之情形，再加上使用長度為 $N$ 的邊之情形，此時 $N$ 為最長的邊。以下以 $N = 10$ 為例，三條邊的情形如下表：

  第一邊	第二邊	第三邊	情形數
  $2$ ~ $8$	$9$	$10$	$7$
  $3$ ~ $7$	$8$	$10$	$5$
  $4$ ~ $6$	$7$	$10$	$3$
  $5$ ~ $5$	$6$	$10$	$1$

  • 由上表可以看出，可以由「等差級數」公式求得 $N = 10$ 的所有狀況：$d = -2$，$a_1 = N - 3$，$n = (a_1 + 1) / 2$。
  $$\begin{align*} S & = a_1 + (a_1 + d) + (a_1 + 2d) + ... + (a_1 + (n - 1)d) \\ & = (a_1 + a_n)n / 2 \\ & = (a_1 + (a_1 + (n - 1)d))n / d \\ & = (2a_1 + (n - 1)d)n / d \\ & = (a_1 - n + 1)n \\ \end{align*}$$
  • 綜合以上，$N = 10$ 的情形數等同於 $N = 9$ 的情形數再加上 $S$。
  • 本題可以先將題目給定範圍的所有情形數都先算出來，再依據輸入印出對應的情形數，要記得使用 long long int。

Input

The input for each case will have only a single positive integer $n$ ($3 \le n \le 1,000,000$). The end of input will be indicated by a case with $n < 3$. This case should not be processed.

Output

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

Sample Input

5
8
0

Sample Output

3
22