Так как в этой задаче не требуется найти способ выдачи сдачи с использованием минимального количества купюр/монет, то можно решать её обычным "жадным" алгоритмом. Ответ в этой задаче всегда будет число, т.е. сдачу автомат сможет выдать всегда, используя монеты по одному рублю. Таким образом ответом может быть M-K единиц, где M - сумма денег, опущенных в автомат, K - стоимость билета.