You are given two integers K and S. Three variable X, Y and Z takes integer values…
- User
You are given two integers K and S. Three variable X, Y and Z takes integer values satisfying 0≤X,Y,Z≤K. How many different assignments of values to X, Y and Z are there such that X + Y + Z = S?
Constraints
- 2≤K≤2500
- 0≤S≤3K
- K and S are integers. Input
The input is given from Standard Input in the following format:
K S
Output
Print the number of the triples of X, Y and Z that satisfy the condition.
Examples
Input
2 2
Output
6
Input
5 15
Output
1
Assistant
We need to solve a problem: Given K and S, count number of integer triples (X, Y, Z) with 0 ≤ X, Y, Z ≤ K such that X+Y+Z = S.
Constraints: K up to 2500, S up to 3K.
We need an efficient O(K) or O(1) solution. Classic combinatorial problem.
Let X, Y, Z ∈ [0, K] integers. Count number of solutions to X+Y+Z = S.
We can treat as stars and bars with upper bounds. Use inclusion-exclusion.
Number of nonnegative integer solutions to X+Y+Z = S without upper bound is C(S+2, 2). Then subtract those where any variable > K.
Define A_x = { X > K }, similarly A_y, A_z. Use inclusion-exclusion:
N = total nonnegative solutions - sum solutions with X≥K+1 + ... + sum with two variables ≥K+1 - sum with three.
But careful: The condition is ≤ K, so > K means ≥ K+1.
Let transform: For X ≥ K+1, set X' = X - (K+1) ≥ 0. Then equation becomes X' + Y + Z = S - (K+1). Number of nonnegative solutions if RHS >= 0: C( (S-(K+1)) + 2, 2 ) = C(S - K + 1, 2). Similarly for others.
For two variables: X ≥ K+1, Y ≥ K+1. Then set X' = X-(K+1), Y' = Y-(K+1). Equation: X'+Y'+Z = S - 2(K+1) = S - 2K - 2. Solutions: if RHS >=0: C( (S-2K-2) + 2, 2 ) = C(S - 2K, 2). Wait: (S-2K-2)+2 = S-2K. So C(S-2K, 2).
Similarly for X and Z, Y and Z.
For three: X, Y, Z each ≥ K+1. Then X'+Y'+Z' = S - 3(K+1) = S - 3K -3. Solutions: C( (S-3K-3)+2, 2 ) = C(S - 3K -1, 2). Because (S - 3K - 3 + 2) = S - 3K -1. So C(S-3K-1, 2) if RHS >=0.
But careful: The inclusion-exclusion formula for upper bounds can be expressed as:
N = ∑{i=0}^{3} (-1)^i * C(3, i) * C( S - i*(K+1) + 2, 2 ), where we interpret binomial coefficient as zero if the top is negative or less than bottom? Actually we need to treat that the number of solutions for a given i (i variables exceeding K) is number of nonnegative solutions to X'+Y'+Z = S - i*(K+1) with the i transformed variables unrestricted and the others nonnegative. So it's C( (S - i(K+1)) + 2, 2 ) if S - i(K+1) >= 0, else 0. But note: In inclusion-exclusion, the terms for i=1,2,3 are counted with sign (-1)^i times combinations of which variables. So overall: N = ∑{j=0}^{3} (-1)^j * C(3, j) * f(S - j*(K+1)), where f(t) = number of nonnegative integer solutions to X+Y+Z = t, which is C(t+2, 2) if t >= 0, else 0. However, note that for j=0, it's C(S+2,2). For j=1: 3 * C(S - (K+1) + 2, 2) if S >= K+1. For j=2: 3 * C(S - 2(K+1) + 2, 2) if S >= 2(K+1). For j=3: C(S - 3(K+1) + 2, 2) if S >= 3(K+1).
But we need to be cautious: This standard inclusion-exclusion counts solutions where each variable is >=0. But we also have upper bound K, not just nonnegative. So indeed the method works.
Let's check with example: K=2, S=2.
Compute: f(2) = C(4,2)=6. f(2-3? i=1: S - (K+1)=2-3=-1, so f(-1)=0. i=2: S-6=-4 =>0. i=3: S-9=-7=>0. So N=6. matches.
Second: K=5, S=15. Then f(15)=C(17,2)=136. i=1: S -6 =9, f(9)=C(11,2)=55, times 3 =165. i=2: S -12=3, f(3)=C(5,2)=10, times 3 =30. i=3: S -18 = -3 =>0. So N = 136 - 165 + 30 = 1. That matches output.
So formula works.
But we need to be careful for cases where S - i(K+1) might be negative but also maybe if the binomial coefficient is defined as zero for negative arguments. So we can compute using max(t, -1) maybe.
We can implement: define comb2(n) = n*(n-1)//2 for n>=1, and 0 if n<2? Actually C(n,2) = n*(n-1)/2 for integer n>=0. But if n<2, should be 0 for negative? Actually combinatorial definition: C(n,2) = n(n-1)/2 for integer n, but if n is negative, it's not defined. But we treat f(t)=0 if t<0. So we compute t = S - i*(K+1). If t<0: f=0 else f = (t+2)(t+1)//2? Wait: f(t) = C(t+2, 2) = (t+2 choose 2) = (t+2)(t+1)/2. Actually (t+2)(t+1)/2, but careful: C(t+2,2) = (t+2)(t+1)/2. For t>=0 integer, that works.
Simplify: f(t) = (t+2)*(t+1)//2 if t>=0 else 0.
Alternatively, we can compute directly using loops over X and compute range for Y, but that would be O(K) which is acceptable since K ≤ 2500, O(K) is fine. But we can also use formula. O(1) is trivial.
However, the constraints are low; O(K) would be fine: iterate X from max(0, S-2K) to min(K, S) maybe? Actually we can iterate X from 0 to K and for each X, Y can range from max(0, S-X-K) to min(K, S-X). Then number of Y values: min(K, S-X) - max(0, S-X-K) + 1, if positive. Sum over X. That's O(K) and K≤2500, worst-case 2500 iterations, trivial. But perhaps we need to be careful about speed? Python can handle easily. But let's aim for O(1) using formula.
But I recall that sometimes inclusion-exclusion with binomial coefficients may have issues when S is small. But we can manage.
We'll implement function solve(K, S) that computes:
def count_triples(K, S): ans = 0 for i in range(0,4): t = S - i*(K+1) if t < 0: continue f = (t+2)*(t+1)//2 ans += ((-1)**i) * comb(3, i) * f return ans
But comb(3,i) is just 1,3,3,1.
Thus:
N = f(S) - 3f(S-(K+1)) + 3f(S-2*(K+1)) - f(S-3*(K+1))
where f(t) = t+2 choose 2 if t>=0 else 0.
That is the answer.
Check edge cases:
-
When S = 0: then only (0,0,0). f(0)=C(2,2)=1, all other f negative => 0. N=1. Good.
-
When S = 3K: then f(3K)=C(3K+2,2). f(3K-(K+1))=2K-1? Actually compute: t1 = 3K - (K+1) = 2K-1, if 2K-1 >=0. f(t1)=C(2K+1,2). t2 = 3K - 2(K+1)=3K-2K-2=K-2. If K>=2, then t2 >=0? For K=2, t2=0; for K>2, t2 positive; but if K=2, t2=0 OK. f(t2)=C(K,2). t3 = 3K - 3(K+1)=3K-3K-3 = -3 <0 =>0. So N = f(3K) -3 f(2K-1) +3 f(K-2). Does this equal 1? Actually for K=2, S=6: f(6)=C(8,2)=28; f(22-1=3): f(3)=C(5,2)=10; f(2-2=0): f(0)=1; So N=28 -310 +31 =28-30+3=1. Good. For K=3, S=9: f(9)=C(11,2)=55; f(23-1=5): C(7,2)=21; f(3-2=1): C(3,2)=3; N=55 -63 +9 =1. So works.
Another edge: K=2500, S=some. The numbers can be big: up to around (3K+2)(3K+1)/2 ~ (75027501)/2 ≈ 28 million, which fits in 64-bit integer easily. So int in Python fine.
Thus solution trivial.
But careful: The formula f(t) = (t+2)*(t+1)//2, but if t is large up to 7500, product up to about 56 million, fits.
Now we need to implement solve() reading input from stdin, printing answer.
We'll provide a Python solution.
But the instruction says "You are given two integers K and S." So we need to read K and S. We'll do:
import sys
def solve(): K, S = map(int, sys.stdin.read().split()) def f(t): if t < 0: return 0 return (t+2)(t+1)//2 ans = f(S) - 3f(S - (K+1)) + 3f(S - 2(K+1)) - f(S - 3*(K+1)) print(ans)
Check with examples.
Now, I'll produce final answer.
But the conversation likely expects a reasoning and solution. Since the user says "You are given two integers K and S...", this is typical from AtCoder problem "XYZ Sum" or something. So answer is short.
I'll output the solution.
But since they ask "How many different assignments", we just print number.
Thus final.
But ensure handling negative arguments: we defined f to return 0 if t<0.
Now, produce final answer. ```python
import sys
def solve() -> None: K, S = map(int, sys.stdin.read().split())
def f(t: int) -> int: """Number of non‑negative integer solutions to X+Y+Z = t.""" if t < 0: return 0 return (t + 2) * (t + 1) // 2 # C(t+2, 2) # Inclusion–exclusion formula ans = (f(S) - 3 * f(S - (K + 1)) + 3 * f(S - 2 * (K + 1)) - f(S - 3 * (K + 1))) print(ans)if name == "main": solve()
-