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

using namespace std;

const bool debug = true;

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; } };

ostream & operator<<(ostream & out, const coinset & coins)
{ if (coins.size() == 0)
  { out << " (none)";
    return out; }
  for (int c: coins)
    out << " " << c;
  return out; }

int numcoins(int amt, coinset coins, int depth = 0)
{ if (debug) cout << setw(depth * 2) << "" << "amount = " << amt << ", coins =" << coins << "\n";
  if (amt == 0)
  { if (debug) cout << setw(depth * 2) << "" << "return 0 because amount is 0\n";
    return 0; }
  if (coins.size() == 0)
  { if (debug) cout << setw(depth * 2) << "" << "return impossible because no coins left\n";
    return 999999999; }
  int coin = coins.back();
  int numwith = 999999999;
  if (coin <= amt)
  { if (debug) cout << setw(depth * 2) << "" << "Trying with " << coin << "\n";
    numwith = 1 + numcoins(amt - coin, coins, depth + 1);
    if (debug) cout << setw(depth * 2) << "" << "with " << coin << " gives " << numwith << " to " << amt << " using" << coins << "\n";
    if (debug) cout << setw(depth * 2) << "" << "Trying without " << coin << ", from " << amt << " using " << coins << "\n";
    int numwithout = numcoins(amt, coins.without_last(), depth + 1);
    if (debug) cout << setw(depth * 2) << "" << "without " << coin << " gives " << numwithout << " to " << amt << " using" << coins << "\n";
    int answer = min(numwith, numwithout);
    if (debug) cout << setw(depth * 2) << "" << "returning " << answer << " from " << amt << " using" << coins << "\n";
    return answer; }
  else
  { if (debug) cout << setw(depth * 2) << "" << "can't use " << coin << "\n";
    if (debug) cout << setw(depth * 2) << "" << "Trying without " << coin << "\n";
    int numwithout = numcoins(amt, coins.without_last(), depth + 1);
    if (debug) cout << setw(depth * 2) << "" << "without " << coin << " gives " << numwithout << " to " << amt << " using" << coins << "\n";
    if (debug) cout << setw(depth * 2) << "" << "returning " << numwithout << " from " << amt << " using" << coins << "\n";
    return 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"; } }