You are splitting a single pool of money among a list of recipients, each of whom is owed some amount. Implement `distribute(amount, recipients)`. `amount` is a pool of nonnegative integer minor currency units (think cents). `recipients` is a list of `[recipient_id, owed]` pairs: `recipient_id` is a unique string and `owed` is a nonnegative integer. Return a list of `[recipient_id, paid]` pairs -- exactly one pair per recipient, in the original input order. ### Fairness contract Let `pool = min(amount, sum(owed))`. The payments you return must total exactly `pool`, and no recipient may be paid more than they are owed. "As evenly as possible" is made unique by **capped water filling**: 1. Find the greatest integer level `L` with `0 <= L <= max(owed)` such that `sum(min(owed[i], L)) <= pool`. 2. Initially pay recipient `i` exactly `min(owed[i], L)`. 3. Let `R = pool - sum(min(owed[i], L))` be the units still unallocated. Give one additional unit to the **first `R` recipients, in input order, whose `owed[i]` is strictly greater than `L`**. A recipient with `owed[i] <= L` never receives an extra unit. This exhausts as much of the pool as the caps allow, never overpays anyone, and leaves at most one unit of difference between any two recipients who are still below their cap. When `pool == sum(owed)`, the bounded definition gives `L = max(owed)`, `R = 0`, and every recipient is paid in full. ### Output semantics - One `[recipient_id, paid]` pair per input recipient -- same count, same order as the input. Never sort the result by `owed` or by id. - `recipient_id` is returned unchanged; `paid` is a nonnegative integer. - Steps 1-3 pin down a single payment vector, so every input has exactly one correct answer. ### Examples ```text amount = 40 recipients = [["a", 10], ["b", 10], ["c", 10], ["d", 10]] result = [["a", 10], ["b", 10], ["c", 10], ["d", 10]] ``` `sum(owed) = 40`, so `pool = 40 = sum(owed)`. `L = 10`, `R = 0`, and everyone is paid in full. ```text amount = 10 recipients = [["a", 2], ["b", 8], ["c", 8]] result = [["a", 2], ["b", 4], ["c", 4]] ``` `pool = 10`. `sum(min(owed, 4)) = 2 + 4 + 4 = 10 <= 10` while `sum(min(owed, 5)) = 12 > 10`, so `L = 4` and `R = 0`. Recipient `a` is capped at 2 and the other two split the rest. ```text amount = 5 recipients = [["a", 10], ["b", 10], ["c", 10]] result = [["a", 2], ["b", 2], ["c", 1]] ``` `pool = 5`. `sum(min(owed, 1)) = 3 <= 5` but `sum(min(owed, 2)) = 6 > 5`, so `L = 1` and `R = 5 - 3 = 2`. All three are above `L`, so the two leftover units go to the first two in input order. ```text amount = 20 recipients = [["a", 3], ["b", 4]] result = [["a", 3], ["b", 4]] ``` `pool = min(20, 7) = 7 = sum(owed)`, so `L = 4`, `R = 0`, and both are paid in full. The 13 unspent units simply stay in the pool. ### Language interface Each language uses the shape its harness marshals naturally; the semantics above are identical everywhere. - **Python** -- `distribute(amount, recipients)`; `recipients` is a list of `[str, int]` two-element lists, and you return a list of `[str, int]` two-element lists. - **JavaScript** -- `distribute(amount, recipients)`; rows are two-element arrays `[string, number]`. - **Java** -- `java.util.List<java.util.List<Object>> distribute(long amount, java.util.List<java.util.List<Object>> recipients)`. Each input row holds a `String` id at index 0 and a `Number` (`Integer` or `Long`, depending on magnitude -- read it with `((Number) row.get(1)).longValue()`) at index 1. Each output row must hold the `String` id and a `Long` payment. - **C++** -- `std::vector<std::pair<std::string, long long>> distribute(long long amount, const std::vector<std::pair<std::string, long long>>& recipients)`; `.first` is the id and `.second` is the amount. ### Follow-up thinking - Why does dividing `pool` evenly and then clipping each share to `owed` fail to exhaust the pool? - Why does sorting by `owed` reveal `L` without ever touching individual currency units? - Why is the original input order still needed after `L` is known?