Parking meter coins
EasyOnline Assessment
Simulate a street parking meter that sells time for coins until it is full.
The meter takes only four coins: 5, 10, 25 and 100 cents. Any other value is not a real coin for this meter and is always rejected (spat back out). Time is sold in blocks of 30 minutes, and one block costs price cents. The meter can hold at most max_minutes minutes (a multiple of 30), which means it can hold at most (max_minutes / 30) * price cents of credit.
Coins are inserted one at a time, in order. For each coin:
- if it is not one of the four coins, it is rejected;
- otherwise, if adding it would push the credit above the most the meter can hold, it is rejected and the credit stays as it was;
- otherwise it is accepted and added to the credit.
A rejected coin does not stop later coins: a smaller coin can still fit when a larger one did not. The meter never gives change, and credit that does not fill a whole block is simply kept (it can combine with later coins, but if the driver stops it buys nothing).
When the coins run out, the time bought is 30 minutes times the number of whole blocks the credit pays for.
Input: coins, the coin values in the order inserted; price, the cost of one 30-minute block in cents; max_minutes, the meter's maximum time.
Output: a list [minutes, rejected], where minutes is the time bought and rejected is the list of rejected coin values in the order they were inserted.
Example 1
- Input:
- [[25,100,25,50,25,5,25],50,120]
- Output:
- [90,[50,25]]
- Explanation
- A block costs 50 and the meter holds 120 minutes, so at most 4 * 50 = 200 cents of credit. 25, 100 and 25 are accepted (150). The 50 is not a real coin and is rejected. 25 more makes 175 and 5 makes 180: both fit. The 25 after that would make 205, above 200, so it is rejected. 180 cents pay for 3 whole blocks: 90 minutes. Result
[90, [50, 25]].
Example 2
- Input:
- [[100,100,25,10,5,25],75,60]
- Output:
- [30,[100,25]]
- Explanation
- A block costs 75 and the meter holds 60 minutes, so at most 150 cents. The 100 fits. The next 100 would make 200, so it is rejected, but the 25 after it fits (125) and so does the 10 (135). The 5 makes 140 and a final 25 would exceed 150, so it is rejected. 140 cents pay for 1 whole block of 75: 30 minutes, and the leftover 65 is wasted. Result
[30, [100, 25]].
Example 3
- Input:
- [[1],25,30]
- Output:
- [0,[1]]
- Explanation
- The only coin inserted is a 1 cent coin, which is not accepted, so no time is bought. Result
[0, [1]].
Constraints
0 <= coins.length <= 3001 <= coins[i] <= 2001 <= price <= 50030 <= max_minutes <= 600, a multiple of 30