Problem 176687 · hard · Phase 01 Prerequisites & Setup

The Vending Machine That Must Make Change

lists · strings · loops · conditionals · functions

Write the controller of a snack machine. Slot i sells an item for prices[i] cents and has stock[i] items. The machine keeps a coin bank bank = [h, q, d, n]: how many 100, 25, 10 and 5 cent coins it holds. Process the list of events in order and return one response string per event.

  • "coin X": if X is 5, 10, 25 or 100, the coin drops into the bank at once, the credit grows by X, and the response is "CREDIT <credit>". Any other value is handed back: "RETURN X".
  • "pick i": checked in this order. If slot i is empty: "SOLD OUT". If the credit is below the price: "NEED <price - credit>". If the change (credit minus price) cannot be paid exactly from the bank: "NO CHANGE". In these three cases nothing changes. Otherwise the item drops, the change leaves the bank, the credit becomes 0, and the response is "VEND i CHANGE h q d n" with the counts of 100, 25, 10 and 5 coins paid out.
  • "cancel": the whole credit is paid back from the bank (always possible, since those coins went in), the credit becomes 0, and the response is "CANCEL h q d n".

Change is always paid with the fewest coins the bank allows. If several ways use equally few coins, pick the one with the most 100s, then the most 25s, then the most 10s.

Examples

Input:  prices = [65, 120], stock = [1, 5], bank = [0, 1, 3, 0],
        events = ["coin 100", "pick 0", "coin 3", "pick 0", "pick 1", "coin 25", "cancel"]
Output: ["CREDIT 100", "VEND 0 CHANGE 0 1 1 0", "RETURN 3", "SOLD OUT", "NEED 120",
         "CREDIT 25", "CANCEL 0 1 0 0"]

Input:  prices = [70], stock = [2], bank = [0, 1, 3, 0], events = ["coin 100", "pick 0"]
Output: ["CREDIT 100", "VEND 0 CHANGE 0 0 3 0"]
Explanation: a quarter first would leave 5 cents that the bank cannot pay.

Input:  prices = [95], stock = [1], bank = [0, 0, 0, 0],
        events = ["coin 100", "pick 0", "coin 5", "pick 0", "cancel"]
Output: ["CREDIT 100", "NO CHANGE", "CREDIT 105", "NO CHANGE", "CANCEL 1 0 0 1"]

Constraints

  • 1 <= len(prices) == len(stock) <= 10; prices are positive multiples of 5.
  • Every pick i has 0 <= i < len(prices); 0 <= len(events) <= 300.
  • The credit never exceeds 1000 cents, and every bank count is at most 60.

Goals

  • Parse command strings and keep machine state in lists
  • Search every coin combination with nested loops when grabbing big coins first fails
  • Apply a fixed order of checks before changing any state
Starting Python…