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

using namespace std;

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

const int one_pound = 240;

int answers[one_pound][6];

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

void whichcoins(int amt, coinset coins)
{ if (amt == 0)
    return;
  if (coins.size() == 0)
    return;
  int coin = coins.back();
  if (coin > amt)
    whichcoins(amt, coins.without_last());
  else
  { int best = numcoins(amt, coins);
    int way1 = 1 + numcoins(amt - coin, coins);
    if (way1 == best)
    { cout << coin << " ";
      whichcoins(amt - coin, coins); }
    else
      whichcoins(amt, coins.without_last()); } }

int main()
{ for (int i = 0; i < one_pound; i += 1)
    for (int j = 0; j < 6; j += 1)
      answers[i][j] = 999999999;
  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";
    whichcoins(amt, coins);
    cout << "\n\n"; } }