Counting Ways to Distribute Candies Among Three Children with Limits

Imagine you are managing a small classroom and need to distribute a specific number of candies among three children. To ensure fairness and manage dietary restrictions, each child has a maximum number of candies they can receive. This problem challenges you to calculate the total distinct ways to distribute the candies while adhering to the total count and individual limits. Such combinatorial problems are fundamental in areas like resource allocation, probability, and discrete mathematics.

Problem Description

You are given two non-negative integers: n, representing the total number of candies to be distributed, and limit, representing the maximum number of candies any single child can receive. You need to distribute exactly n candies among three children. Each child must receive a non-negative integer number of candies, and no child can receive more than limit candies.

Your task is to find the total number of distinct ways to distribute the candies. A "way" is defined by a unique tuple (c1, c2, c3), where c1 is the candies for child 1, c2 for child 2, and c3 for child 3. The following conditions must be met for each way:

1. c1 + c2 + c3 = n (The sum of candies must equal n).
2. 0 <= c1 <= limit
3. 0 <= c2 <= limit
4. 0 <= c3 <= limit

You should return a single integer representing the count of all such distinct tuples (c1, c2, c3).

Examples

Example 1:

Input:
  n = 5
  limit = 2
Output: 3
Explanation:
The total number of candies is 5, and each child can receive a maximum of 2 candies.
The valid ways (tuples) are:
- (1, 2, 2)
- (2, 1, 2)
- (2, 2, 1)
Any other combination would violate the sum constraint or the per-child limit. For instance, (0, 2, 3) is invalid because 3 > limit.

Example 2:

Input:
  n = 10
  limit = 3
Output: 0
Explanation:
The total number of candies is 10, and each child can receive a maximum of 3 candies.
The absolute maximum candies that can be distributed among three children, where each receives at most 3, is 3 * 3 = 9 candies.
Since n (10) is greater than this maximum possible sum (9), it's impossible to distribute 10 candies under these constraints.

Example 3:

Input:
  n = 1
  limit = 1
Output: 3
Explanation:
The total number of candies is 1, and each child can receive a maximum of 1 candy.
The valid ways (tuples) are:
- (1, 0, 0)
- (0, 1, 0)
- (0, 0, 1)

Constraints

• 0 <= n <= 10^5
• 0 <= limit <= 10^5
• The problem requires an efficient solution. A brute-force approach iterating through all possible combinations for each child (e.g., three nested loops) will be too slow given the maximum values of n and limit. Consider solutions that achieve a complexity better than O(n * limit) or similar polynomial time with large exponents.

Notes

• This problem can be approached using combinatorial techniques, often related to the "stars and bars" method with an inclusion-exclusion principle to handle the upper bound constraints (<= limit).
• Remember that the order of candies distributed among the children matters (e.g., (1,2,2) is distinct from (2,1,2)).
• Pay close attention to the edge cases, such as when n is 0, when limit is 0, or when n is larger than 3 * limit.
• The number of children is fixed at 3.