<p>You are given two positive integers <code>n</code> and <code>limit</code>.</p>

<p>Return <em>the <strong>total number</strong> of ways to distribute </em><code>n</code> <em>candies among </em><code>3</code><em> children such that no child gets more than </em><code>limit</code><em> candies.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 5, limit = 2
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are 3 ways to distribute 5 candies such that no child gets more than 2 candies: (1, 2, 2), (2, 1, 2) and (2, 2, 1).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3, limit = 3
<strong>Output:</strong> 10
<strong>Explanation:</strong> There are 10 ways to distribute 3 candies such that no child gets more than 3 candies: (0, 0, 3), (0, 1, 2), (0, 2, 1), (0, 3, 0), (1, 0, 2), (1, 1, 1), (1, 2, 0), (2, 0, 1), (2, 1, 0) and (3, 0, 0).
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 10<sup>6</sup></code></li>
	<li><code>1 &lt;= limit &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def distributeCandies(self, n: int, limit: int) -> int:
        max_n = limit*3
        if n > max_n:
            return 0
        elif n==max_n:
            return 1

        p = 0
        for i in range(min(limit, n)+1): # first child's 
            # possiblities for other children are gated by the limit and the remaining candies
            remain = n - i
            if limit*2>=remain:
                if limit >= remain:
                    p += remain + 1
                else:
                    if remain % 2 == 0:
                        base_split = remain // 2
                        p += (limit - base_split) * 2 + 1
                    else:
                        base_split = (remain - 1) // 2
                        p += (limit - base_split) * 2
        
        return p

# print(Solution().distributeCandies(10,1))  # 0
# print(Solution().distributeCandies(10,2))  # 0
# print(Solution().distributeCandies(10,3))  # 0
# print(Solution().distributeCandies(10,4))  # 6
# print(Solution().distributeCandies(10,5))  # 21
# print(Solution().distributeCandies(10,6))  # 36
# print(Solution().distributeCandies(10,7))  # 48
# print(Solution().distributeCandies(10,8))  # 57
# print(Solution().distributeCandies(10,9))  # 63
# print(Solution().distributeCandies(10,10)) # 66
16200