2015年3月8日 星期日

[TIOJ 1467] 三角蕃的花圃

作法:

反過來作,考慮全部的可以把木棍切成三條長度不為0的切法,共有C( n-1 , 2 ) 種( 並且是有序的切法 ),那麼不符合條件的就是其中一個 >= n 的一半的,可以知道如果最長邊 = x ,那剩下兩邊就有 n - x - 1 種選法,所以只要扣掉 x 從 n 的一半一直加到 n-1 的那個值乘以3就好了( 乘以3是因為最長邊可以放三個位置 )。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
 
main()
{
    LL n ;
    while(scanf("%lld",&n)!=EOF)
    {
        LL k=(n+1)/2 ;
        LL ans=(n-1)*(n-2)/2 ;
        ans=ans-3*((n-1)*(n-k)-(n+k-1)*(n-k)/2) ;
        printf("%lld\n",ans) ;
    }
}
 

沒有留言:

張貼留言