[Codeforces Round #317] Lengthening Sticks

9
19
2015

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.

题目大意：给出3个数a，b，c。可以增加它们的长度，但增加的总长度不能超过l（当然也可以不增加）。求增加后能使它们构成三角形的方案数。

首先根据容斥原理，所求的方案数为总方案数减去不能构成三角形的方案数。

首先求总方案数。可以把l分割成四部分：$l=l_a+l_b+l_c+unused$，即分别分给a，b，c的长度和没有使用的部分，问题转化为求这四个部分非负的情况下使这个等式成立的方案数，用隔板法可以得到方案数为$C^3_{l+3}$。

然后是求不能构成三角形的方案数。先假设$a+l_a$为最长边，之后同样要设另外两条边为最长边，并把三种情况求出的结果加起来。

易得下面两个等式

$a+l_a\ge b+l_b+c+l_c$

$l_a+l_b+l_c\le l$

移项得

$l_b+l_c\le a-b-c+l_a$

$l_b+l_c\le l-l_a$

那么设$x=\min\left( a-b-c+l_a,l-l_a\right)$，就有

$l_b+l_c\le x$

和求总方案数时一样，可以列出$x=l_b+l_c+unused$，得方案数为$C^2_{x+2}$。

最终答案为

$C^3_{l+3}-\\
\sum_{i=0}^l\left( C^2_{\min\left( a-b-c+i,l-i\right) +2}+C^2_{\min\left( b-a-c+i,l-i\right) +2}+C^2_{\min\left( c-a-b+i,l-i\right) +2}\right)$

代码在此。

Category: 题解 | Tags: 数学 Codeforces 组合数学 | Read Count: 425

Stalker's Blog

I am here in the shadows.