codeforces 571A-Lengthening Sticks(结合+容斥)

codeforces 571A--Lengthening Sticks(组合+容斥)

You are given three sticks with positive integer lengths of a, b, and c centimeters. You can increase length of some of them by some positive integer number of centimeters (different sticks can be increased by a different length), but in total by at most l centimeters. In particular, it is allowed not to increase the length of any stick.

Determine the number of ways to increase the lengths of some sticks so that you can form from them a non-degenerate (that is, having a positive area) triangle. Two ways are considered different, if the length of some stick is increased by different number of centimeters in them.

Input

The single line contains 4 integers a, b, c, l (1 ≤ a, b, c ≤ 3·105, 0 ≤ l ≤ 3·105).

Output

Print a single integer — the number of ways to increase the sizes of the sticks by the total of at most l centimeters, so that you can make a non-degenerate triangle from it.

Sample test(s)

input
1 1 1 2

output
4

input
1 2 3 1

output
2

input
10 2 1 7

output
0

Note

In the first sample test you can either not increase any stick or increase any two sticks by 1 centimeter.

In the second sample test you can increase either the first or the second stick by one centimeter. Note that the triangle made from the initial sticks is degenerate and thus, doesn't meet the conditions.

题目链接：点击打开链接

题目大意：给出三条边的长度，可以给任意一条边增加任意的长度，但是增加的长度的总和不能超过l，问有多少种增加的方法，可使得三条边任然能组成一个三角形。

用总的方法数-不能组成三角形的方法数

首先求出所有的能增加的方法，如果三条边增加的长度和是l，那么一共有C(l+2,2)种，计算出从0到l的所有的方法。

然后计算不能组成三角形的方法，如果最长边>=另外两边之和，那么就不是三角形，所以分别枚举a+i,b+i,c+i为最长边，然后计算有多少种不可能的办法。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
#define LL __int64
LL sum[300100] ;
LL solve(int a,int b,int c,int l) {
    if( a < b+c ) return (LL)0 ;
    LL ans = min(a-b-c,l) ;
    return (ans+1)*(ans+2)/2 ;
}
int main() {
    int a , b , c , l ;
    LL i , ans ;
    while( scanf("%d %d %d %d", &a, &b, &c, &l) != EOF ) {
        sum[0] = 1 ;
        for(i = 1 ; i <= l ; i++) {
            sum[i] = (i+1)*(i+2)/2 + sum[i-1] ;
        }
        ans = sum[l] ;
        for(i = 0 ; i <= l ; i++) {
            ans -= solve(a+i,b,c,l-i) ;
            ans -= solve(b+i,a,c,l-i) ;
            ans -= solve(c+i,a,b,l-i) ;
        }
        printf("%I64d\n", ans) ;
    }
    return   0 ;
}

codeforces 571A-Lengthening Sticks(结合+容斥)

相关推荐