#include <iostream>
#include <map>
#include <string>
using namespace std;

struct Item { string name; int price; int stock; };
struct Machine;

// Each state answers the events itself; the machine only points at the current one.
struct State {
    virtual string name() const = 0;
    virtual void insert(Machine& m, int coin) = 0;
    virtual void select(Machine& m, const string& code) { cout << "select " << code << ": ignored in " << name() << "\n"; }
    virtual void dispense(Machine& m) {}
};
struct Idle : State { string name() const override { return "Idle"; } void insert(Machine& m, int coin) override; };
struct HasMoney : State {
    string name() const override { return "HasMoney"; }
    void insert(Machine& m, int coin) override;
    void select(Machine& m, const string& code) override;
};
struct Dispensing : State {
    string name() const override { return "Dispensing"; }
    void insert(Machine& m, int coin) override { cout << "insert " << coin << ": busy, returned " << coin << "\n"; }
    void dispense(Machine& m) override;
};
struct OutOfStock : State {
    string name() const override { return "OutOfStock"; }
    void insert(Machine& m, int coin) override { cout << "insert " << coin << ": sold out, returned " << coin << "\n"; }
};
// States hold no data of their own, so one shared instance of each is enough.
Idle IDLE; HasMoney HAS_MONEY; Dispensing DISPENSING; OutOfStock OUT_OF_STOCK;

struct Machine {
    map<string, Item> items;
    State* state = &IDLE;
    int balance = 0;
    Item* selected = nullptr;
    void move(State* next, const string& event, const string& note) {
        cout << event << ": " << state->name() << " -> " << next->name() << (note.empty() ? "" : ", " + note) << "\n";
        state = next;
    }
    // Greedy: the largest coin that fits, again and again (optimal for 10/5/2/1).
    static string change(int amount) {
        string out;
        for (int c : {10, 5, 2, 1}) while (amount >= c) { out += (out.empty() ? "" : "+") + to_string(c); amount -= c; }
        return out.empty() ? "none" : out;
    }
};

void Idle::insert(Machine& m, int coin) { m.balance += coin; m.move(&HAS_MONEY, "insert " + to_string(coin), "balance " + to_string(m.balance)); }
void HasMoney::insert(Machine& m, int coin) { m.balance += coin; cout << "insert " << coin << ": balance " << m.balance << "\n"; }
void HasMoney::select(Machine& m, const string& code) {
    Item& item = m.items.at(code);
    if (item.stock == 0) { cout << "select " << code << ": " << item.name << " sold out\n"; return; }
    if (m.balance < item.price) {
        cout << "select " << code << ": " << item.name << " costs " << item.price << ", insert " << item.price - m.balance << " more\n";
        return;
    }
    m.selected = &item;
    m.move(&DISPENSING, "select " + code, "");
    m.state->dispense(m);
}
void Dispensing::dispense(Machine& m) {
    Item& item = *m.selected;
    item.stock--;
    string change = Machine::change(m.balance - item.price);
    m.balance = 0;
    bool empty = true;
    for (auto& [code, i] : m.items) if (i.stock > 0) empty = false;
    m.move(empty ? (State*)&OUT_OF_STOCK : &IDLE, "dispense", item.name + ", change " + change);
}

int main() {
    Machine m;
    m.items["A1"] = {"Chips", 15, 1}; m.items["A2"] = {"Juice", 22, 1};
    m.state->insert(m, 10); m.state->select(m, "A1"); m.state->insert(m, 10); m.state->select(m, "A1");
    m.state->insert(m, 10); m.state->insert(m, 10); m.state->insert(m, 10); m.state->select(m, "A2");
    m.state->insert(m, 10);
}