10.3

Idea: count the non-negative integer solutions of [math]1\cdot f+2\cdot t+3\cdot h=n[/math], where f = free-throws, t = 2-pointers, h = 3-pointers. 1. Loop over the possible numbers of 3-pointers [math]h=0.. \lfloor n/3 \rfloor[/math]. For each h the remaining points are [math]r=n-3h[/math]. 2. Now solve [math]1\cdot f+2\cdot t=r[/math]. This is a standard “coin-change” sub-problem whose solutions are t = 0 .. ⌊r/2⌋ (and f = r−2t), i.e. [math]\lfloor r/2\rfloor+1[/math] possibilities. 3. Sum these counts for every h. Putting that into code:

def mixes(n: int) -> int: ways = 0 for h in range(n//3 + 1): # 3-pointers r = n - 3*h # points still to score ways += r//2 + 1 # choices for (f,t) return ways

Complexity: • Time O(n) (the loop runs ≤ n/3+1 times). • Memory O(1). Example: n = 5 h = 0 → r = 5 → r//2+1 = 3 h = 1 → r = 2 → r//2+1 = 2 Total ways = 3+2 = 4, matching (5,0,0), (2,0,1), (1,2,0), (0,1,1).

Back to Chapter 10