#include <iostream>
#include <iomanip>
#include <vector>

using namespace std;

const bool debug = false;

class coinset: public vector<int>
{ public:

    coinset(initializer_list<int> values): vector<int>(values)
    { }

    coinset without_last()
    { coinset copy = * this;
      copy.pop_back();
      return copy; } };

int numcoins(int amt, coinset coins)
{ if (amt == 0)
    return 0;
  if (coins.size() == 0)
    return 999999999;
  int coin = coins.back();
  int numwith = 999999999;
  if (coin <= amt)
    numwith = 1 + numcoins(amt - coin, coins);
  int numwithout = numcoins(amt, coins.without_last());
  return min(numwith, numwithout); }

int main()
{ coinset coins({ 1, 3, 6, 12, 24, 30 });
  while (true)
  { int amt;
    cout << "Amount to give change for: ";
    cin >> amt;
    if (cin.fail())
    { cout << "\n";
      break; }
    int num = numcoins(amt, coins);
    cout << "\n" << num << " coins will do it\n\n"; } }