1042. Change for Every Customer
A stall sells one item for 5. Customers arrive in a fixed order and each pays with a single note worth 5, 10 or 20. You start with no money and must hand back the correct change immediately, using only notes you have already taken.
Print yes if every customer can be served, or no if you get stuck.
5 5 5 10 20 -> yes
5 5 10 10 20 -> no the second 10 takes your last 5, so the 20 cannot be changed
5 20 -> no 15 change from a single 5
10 -> no you have nothing to give
A 10 needs 5 back. A 20 needs 15 back, which is either one 10 and one 5, or three 5s. Nothing else is possible, since you never have a note smaller than 5.
## What most people try first
Search. At each 20, try both ways of making 15 and see whether either leads to a complete run.
That branches at every 20, so the worst case is 2^(number of 20s) and the input allows
100000 customers.
Memoising on (position, fives, tens) fixes the blowup and is a fine solution. It is also
unnecessary, because one of the two choices is never worse than the other.
## The rule
Always pay the 15 with a 10 and a 5 when you can. Only fall back on three 5s.
fives = 0, tens = 0
for each note:
5 -> fives += 1
10 -> if fives == 0: answer no; fives -= 1, tens += 1
20 -> if tens >= 1 and fives >= 1: tens -= 1, fives -= 1
else if fives >= 3: fives -= 3
else: answer no
## Why the 10 must go first
A 5 is strictly more useful than a 10. Every future demand a 10 can satisfy, a 5 can satisfy too, because a 10 is only ever usable as part of the 15 owed on a 20, and that same 15 can also be paid with 5s. The reverse is false: a 10 can never help with the 5 owed on a 10.
So compare the two states after a 20. Paying with a ten and a five leaves
(fives - 1, tens - 1). Paying with three fives leaves (fives - 3, tens). The first has
two more 5s and one fewer 10. Trade the one extra 10 in the second state against one of the two
extra 5s in the first: the first state still has a spare 5 and can meet every demand the second
can. So it is never worse, and the branch disappears.
That is an exchange argument on the STATE rather than on the schedule, and it is the shortest one in this block.
## Note that the 10 case has no choice at all
A 10 must be changed with a 5, because there is nothing smaller. The only decision in the whole problem is at a 20, which is why the argument above is enough.
## The trap
Forgetting that a 10 also CONSUMES a 5. A version that only counts 20s passes
5 5 5 10 20 and fails 5 5 10 10 20, which is in the tests for exactly that reason.
## Overflow
Counts are bounded by the number of customers, 100000. Nothing here approaches the 32 bit
limit of 2147483647.
## Cost
Time O(n). Space O(1).
Constraints - `1 ≤ n ≤ 100000` - each note is exactly `5`, `10` or `20`
Input
The first line contains an integer n, the number of customers.
The second line contains n space-separated integers, each 5, 10 or 20, in arrival order.
Output
Print the single lowercase word yes if every customer can be given correct change, or no otherwise. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.