Problem 11401 Triangle Counting，木棍組合總和

給你 1、2、...、n 個長度的木棍，要你去組合它們成為不同的三角形，將這些組成三角形的總和起來，就是答案。

例如： n = 6，利用「任意兩邊之和等於或小於第三邊而不能構成三角形」的概念，所以有 234、245、256、345、346、356、456 共 7 種組合。

其實這也不需要傷腦筋去算出來，因為論壇上已有公式了。f(3) = 0，f(4) = 1，當i > 4 時，f(i) = f(i - 1) + j， j = i * (i-1) - (i+1) * (i-b) - b * (b-1)，其中 b = i / 2 + 1。這裡還是提供 C 語言程式碼給大家參考：

unsigned long long int ans[1000001];

void create()
{
    int i;
    unsigned long long int s, b, now;
    ans[3] = 0;
    ans[4] = 1;
    for (i = 5; i < 1000001; i ++)
    {
        s = i;
        b = i / 2 + 1;
        now = s*(s-1)-(s+1)*(s-b)-b*(b-1);
        ans[i] = ans[i - 1] + now;
    }
}

函式建構出來後，只需再主程式裡面針對索引印出答案就可以了。

By David.K

p11401題目連結
回ACM題庫目錄
回首頁