題目連結: http://codeforces.com/contest/571/problem/A
# 內容
給出 a,b,c,l，要求 a+x,b+y,c+z 構成三角形，x+y+z<=l，成立的 x,y,z 有多少種。
# 思路
答案 = 所有狀況 - 不滿足條件的狀況
在 l 全用的狀況下:
l = 1 : 3 = 1 + 2
l = 2 : 6 = 1 + 2 + 3
l = 3 : 10 = 1 + 2 + 3 + 4
...........
l = i : 1 + 2 + .... + i+1 => (i+2)*(i+1)/2
不滿足的狀況就是：一邊 >= 任兩邊相加
a + i (加長的) >= b + c + (l - i) (剩下的), i<=l
在各個討論就好
# 程式碼
int cal(int a,int b,int c,int l) { | |
int total=0; | |
//a+i>=b+c => i>=b+c-a and i>=0 | |
for(int i=max(b+c-a,0LL);i<=l;++i) { | |
int x=min(l-i,a+i -b-c ); | |
total+=(1+x)*(2+x)/2; | |
} | |
return total; | |
} | |
signed main(){ | |
int a,b,c,l;ios::sync_with_stdio(false); | |
cin>>a>>b>>c>>l; | |
int total = 0; | |
for(int i = 0;i<=l;i++) | |
total +=(i+1)*(i+2)/2; | |
total -=cal(a,b,c,l); | |
total -=cal(b,a,c,l); | |
total -=cal(c,b,a,l); | |
cout<<total; | |
} |
