#include <iostream>
#include <iomanip>
#include <set>
#include <string>
#include <ctime>
using namespace std;

int main() {
    int snacks_arr[] = { 94,134,233,426,496,915,917,1072,1431,1553,1569,1580,
          1622,1649,1673,1886,1922,2094,2139,2249,2437,2491,2569,2714,2812 };
    set<int> snacks(snacks_arr, snacks_arr + sizeof(snacks_arr)/sizeof(int));
    int prices[] = { 7,7,7,11,13,13,13,16,19,19,21,23,27,37,41,56,56,61,73,77,97 };
    bool used[21], init[21] = { false };
    int  terms[5];
    int i, j, result, attempts=0;
    srand( time( 0 ) );
    
    while (1) {
        memcpy( used, init, sizeof(init) );
        i = 0;
        while (i < 5) {
            j = rand() % 21;
            while (used[j])
                j = rand() % 21;
            used[j] = true;
            terms[i++] = prices[j];
        }
        attempts++;
        result = terms[0] * terms[1] + terms[2] - terms[3] + terms[4];
        if (snacks.find(result) != snacks.end()) {
            snacks.erase(result);
            for (int k=0; k < 5; k++)
                cout << setw(3) << terms[k];
            cout << setw(5) << result;
            cout << "    attempts is " << setw(5) << attempts << endl;
            attempts = 0;
            if (snacks.size() == 1)
                break;
        }
    }

    cout << "unreachable is ";
    set<int>::iterator it;
    for (it = snacks.begin(); it != snacks.end(); ++it)
        cout << *it << ' ';
    cout << endl;
}

/************************
 37 13 23 19 11  496    attempts is    40
 11  7 21 41 77  134    attempts is    67
 16 13 19  7 13  233    attempts is    93
 27 56 13 13 41 1553    attempts is   125
 56 16  7  7 19  915    attempts is    97
 56 41 11 77 19 2249    attempts is   418
 56 16 13 13 21  917    attempts is    76
 16 97 21  7 56 1622    attempts is   328
  7  7 21 13 37   94    attempts is   437
 16 97 13 23 27 1569    attempts is   810
 19 97 37  7 13 1886    attempts is   478
 61  7 13 27 13  426    attempts is   566
 21 73 56 13 97 1673    attempts is   320
 56 19 13 61 56 1072    attempts is   479
 56 27 19  7 56 1580    attempts is   714
 97 21 11 27 73 2094    attempts is   331
 37 73  7  7 13 2714    attempts is  2526
 27 77 41 37 56 2139    attempts is  1592
 27 97 16 77 11 2569    attempts is    68
 77 21 56 61 37 1649    attempts is  5470
 19 77 13 56 11 1431    attempts is  7123
 27 73  7 97 41 1922    attempts is   650
 77 37 13 61 11 2812    attempts is 67909
 41 61 56 73  7 2491    attempts is 142666
unreachable is 2437 
*************************/


#include <iostream>
#include <iomanip>
#include <set>
#include <sstream>
#include <string>
using namespace std;

int snacks_arr[] = { 94,134,233,426,496,915,917,1072,1431,1553,1569,1580,
      1622,1649,1673,1886,1922,2094,2139,2249,2437,2491,2569,2714,2812 };
set<int> snacks(snacks_arr, snacks_arr + sizeof(snacks_arr)/sizeof(int));
set<int> snacks_remaining( snacks );
set<string> solutions;
stringstream ss;

void test_terms( int terms[] ) {
  int result = terms[0] * terms[1] + terms[2] - terms[3] + terms[4];
  if (snacks.find(result) == snacks.end())
    return;
  snacks_remaining.erase( result );
  ss.str("");
  ss << setw(4) << result << ' ';
  for (int k=0; k < 5; k++)
    ss << setw(3) << terms[k];
  solutions.insert( ss.str() );
}

int main() {
  int prices[] = { 7,7,7,11,13,13,13,16,19,19,21,23,27,37,41,56,56,61,
        73,77,97 };
  int terms[5];
    
  for (int i=0;   i < 21 - 4; i++)
    for (int j=i+1; j < 21 - 3; j++)
      for (int k=j+1; k < 21 - 2; k++)
        for (int l=k+1; l < 21 - 1; l++)
          for (int m=l+1; m < 21;     m++) {
            terms[0] = prices[i];
            terms[1] = prices[j];
            terms[2] = prices[k];
            terms[3] = prices[l];
            terms[4] = prices[m];
            test_terms( terms );
            while (next_permutation( terms, terms+5 ))
              test_terms( terms );
          }

  set<string>::iterator sol_it;
  for (sol_it = solutions.begin(); sol_it != solutions.end(); ++sol_it)
    cout << *sol_it << endl;

  cout << "total is " << solutions.size() << ", unreachable is ";
  set<int>::iterator it;
  for (it = snacks_remaining.begin(); it != snacks_remaining.end(); ++it)
    cout << *it << ' ';
  cout << endl;
}

/*************************
  94   7  7  7 23 61
  94   7  7 11  7 41
  94   7  7 11 27 61
...
 134   7  7  7 19 97
 134   7  7 11 23 97
 134   7  7 19  7 73
...
2714  97 27 77 19 37
2714  97 27 77 23 41
...
2812  77 37 19 97 41
2812  77 37 23 73 13
2812  77 37 41 97 19
count is 3288, unreachable is 2437 
*************************/