Codeforces #317 C.Lengthening Sticks(数学)

　C. Lengthening Sticks

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

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分成3份有多少种方法呢？

有l个点，那么就有l + 1个空位，你可以在其中选择3个插入，是不是很像组合数，但是你选择的这三个空位是可以重复的，所以我们再增加两个空位，用这两个空位代表重复的情况，可以理解为选择了这个特殊空位就和选了上一个非特殊空位一样，所以如果两个特殊空位都选，那就代表了插入位置的重复。

插入的位置把l分成了3段，那么从l + 1 + 2中选3个 （C(l + 3)(3)）即为总个数

公式为(l + 1) * (l + 2) * (l + 3) / 6

如果这样说不能理解，那么换一个方式，如果把第一个断点放在第一个空位上，

把第二个断点放在第一个空位上，那么第三个断点可以选择l+1个； 把第二个断点放在第二个空位上，第三个断点可以选l个

	第一个断点位置第二个断点位置	1	2	3	4	5	6			L	L + 1
	1	L + 1	L	L - 1	L - 2	L - 3	L - 4	...	3	2	1
	2		L	L - 1	L - 2	L - 3	L - 4	...	3	2	1
	3			L - 1	L - 2	L - 3	L - 4	...	3	2	1
	4				L - 2	L - 3	L - 4	...	3	2	1
	5					L - 3	L - 4	...	3	2	1
	6						L - 5	...	3	2	1
								...	3	2	1
	L								3	2	1
	L + 1										1

将表中数据求和，需要用到1 ^ 2 + 2 ^ 2 + ... + n ^ 2

 

处理出总情况之后

枚举增加的长度，假如 a + i(增加长度) <= b + c

那么就把不符合情况的删掉，a分配了i， b + c最多为l - i， 又要是不合法的情况所以b + c 一定要比a + i小于等于，所以增加的也不能超过a + i - b - c；

然后就是把这个 0到这个最小值 分别分配给其余两数 分配n时， 方案为n + 1；

所以总方案为(min + 1) * (min + 2) / 2;

#include <stdio.h>
#include <algorithm>
using namespace std;
long long solve(long long x) {            //这里的long long返回不要忘了
    return (x + 1) * (x + 2) >> 1;
}
int main() {
    long long a, b, c, l;
    scanf("%I64d%I64d%I64d%I64d", &a, &b, &c, &l);
    long long nr = (l + 1) * (l + 2) * (l + 3)  / 6;
    for (long long i = 0; i <= l; i++) {
        if (a + i >= b + c) nr -= solve(min(l - i, a + i - b - c));
        if (b + i >= a + c) nr -= solve(min(l - i, b + i - a - c));
        if (c + i >= a + b) nr -= solve(min(l - i, c + i - a - b));
    }
    printf("%I64d
", nr);
    return 0;
}