total identical cans of food on a hike. Each of them is willing to take anywhere from zero to cap cans inclusive, and every can must be taken.
In how many ways can the cans be shared out? Two ways differ if some particular friend gets a different number of cans: (2, 1, 0) and (0, 1, 2) count separately.
Both numbers go up to a million, so trying every pair of shares may be too slow.total=4, cap=2 → 6
The valid splits are (2, 2, 0), (2, 0, 2), (0, 2, 2), (2, 1, 1), (1, 2, 1) and (1, 1, 2): six ways.
total=7, cap=2 → 0
Three people carrying at most 2 each can take only 6 units, which is not enough for 7.
total=2, cap=5 → 6
total ≤ 10⁶cap ≤ 10⁶total=4, cap=2
6
Run checks the first 3 tests in your browser. Submit checks all 93 tests on the server, hidden ones included.