問題
http://community.topcoder.com/stat?c=problem_statement&pm=4811&rd=8081
１辺の最小の長さと、最大の長さが与えられる。
このとき、とりうる三角形の数を求める。
ただし、回転して同じ三角形になる場合は同じものとみなす。
答えが10^9を超える場合は-1を返す。
解き方
２重ループでは計算量として間に合わない、はずなのですが
10^9以上は-1を返すので２重ループで収まります。
コード
class TriCount {
public: int count(int minLength, int maxLength) {
long long ret=0LL;
FORE(i,minLength,maxLength+1){
FORE(j,i,maxLength+1){
ret+=min(maxLength,i+j-1)-j+1;
if(ret>1000000000)return -1;
}
}
return ret;
}
};
public: int count(int minLength, int maxLength) {
long long ret=0LL;
FORE(i,minLength,maxLength+1){
FORE(j,i,maxLength+1){
ret+=min(maxLength,i+j-1)-j+1;
if(ret>1000000000)return -1;
}
}
return ret;
}
};