#include <iostream>
#include <iomanip>

using namespace std;

const int coins[] = { 0, 1, 3, 6, 12, 24, 30 };
const int coins_in_set = sizeof(coins) / sizeof(coins[0]);

const int one_pound = 240;

int answers[one_pound][coins_in_set + 1];

//
// the original recursive function
//
// int numcoins(int amt, int coins_allowed = coins_in_set)
// { if (amt == 0)
//     return 0;
//   if (coins_allowed == 0)
//     return 999999999;
//   int coin = coins[coins_allowed - 1];
//   int numwith = 999999999;
//   if (coin <= amt)
//     numwith = 1 + numcoins(amt - coin, coins_allowed);
//   int numwithout = numcoins(amt, coins_allowed - 1);
//   return min(numwith, numwithout); }
//

void prepare()
{ for (int coin_number = 0; coin_number < coins_in_set; coin_number += 1)
    answers[0][coin_number] = 0;
  for (int amt = 1; amt < one_pound; amt += 1)
    answers[amt][0] = 999999999;
  for (int coin_number = 1; coin_number < coins_in_set; coin_number += 1)
  { for (int amt = 1; amt < coins[coin_number]; amt += 1)
      answers[amt][coin_number] = answers[amt][coin_number - 1];
    for (int amt = coins[coin_number]; amt < one_pound; amt += 1)
      answers[amt][coin_number] = min(answers[amt][coin_number - 1],
                                      1 + answers[amt - coins[coin_number]][coin_number]); } }

void whichcoins(int amt)
{ int coins_allowed = coins_in_set - 1;
  while (true)
  { if (amt == 0)
      break;
    if (coins_allowed == 0)
      break;
    int coin = coins[coins_allowed];
    if (coin > amt)
      coins_allowed -= 1;
    else
    { int best = answers[amt][coins_allowed];
      int way1 = 1 + answers[amt - coin][coins_allowed];
      if (way1 == best)
      { cout << coin << " ";
        amt -= coin; }
      else
        coins_allowed -= 1; } }
  cout << "\n"; }

int main()
{ prepare();
  while (true)
  { int amt;
    cout << "Amount to give change for: ";
    cin >> amt;
    if (cin.fail())
    { cout << "\n";
      break; }
    int num = answers[amt][coins_in_set - 1];
    cout << "\n" << num << " coins will do it\n";
    whichcoins(amt);
    cout << "\n"; } }