//Are Toy Problems Useful?
//in Selected Papers on Computer Science by Knuth (p.172)

#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <set>
#include <unordered_map> // faster than map
#include <algorithm>
#include <ctime>
#define SQRT sqrtl
typedef long double real;
//#define SQRT sqrt
//typedef double real;
typedef unsigned int uint;
using namespace std;

const real DELTA = 1000.;
const uint N = 50;
const uint sizeA = 20;

int getKey(real x)
{
  return static_cast<int>((x - floor(x)) * 1e8);
}

real getSum(uint code, vector<real>* group, bool ignoreLast)
{
  real sum = 0;
  uint size = group->size();
  if (ignoreLast) --size;
  for (uint i = 0; i < size; ++i) if (code >> i & 1) sum += (*group)[i];
  return sum;
}

void printSolution(set<int>* solution)
{
  real sum = 0;
  stringstream ss;
  for (auto i : *solution) {
    sum += SQRT(i);
    ss << i << ",";
  }
  string str = ss.str();
  cout << setprecision(30) << sum << ": {" << str.substr(0, str.size()-1) << "}" << endl;
}

int main()
{
  auto start = clock();

  real dummy;
  real goal = 0;
  vector<int> all, a, b, c;
  vector<real> groupA, groupB, groupC; //平方根を計算しておく
  for (uint i = 1; i <= N; ++i) {
    all.push_back(i); //{1, 2, ..., 50}
    real t = SQRT(i);
    goal += t;
    if (t == floor(t)) {
      c.push_back(i); //{1, 4, 9, 16, 25, 36, 49}
      groupC.push_back(t);
    }
    else if (a.size() < sizeA) {
      a.push_back(i); //{2, 3, 5, 6, 7, 8, 10, 11, 12, 13,...
      groupA.push_back(t);
    }
    else {
      b.push_back(i);
      groupB.push_back(t);
    }
  }
  goal /= 2.;
  real fracPartOfGoal = modf(goal, &dummy);

  //aのsubset sumを計算し、記憶する
  unordered_multimap<int, pair<int, real>* > subsetSumOfA; //キー：概数、値：codeAと和のペア
  for (uint codeA = 0; codeA < (1u << groupA.size()); ++codeA) {
    real sumA = getSum(codeA, &groupA, false);
    int key = getKey(sumA);
    auto p = new pair<int, real>(codeA, sumA);
    subsetSumOfA.insert(pair<int, pair<int, real>* >(key, p));
  }

  //bのsubset sumを計算する
  real minDelta = DELTA;
  int codeAforMinDelta = 0, codeBforMinDelta = 0;
  real sumAforMinDelta = 0, sumBforMinDelta = 0;
//#pragma omp parallel
  for (uint codeB = 0; codeB < (1u << (groupB.size() - 1)); ++codeB) { //bの1つの要素は決めておいてよい
    real sumB = getSum(codeB, &groupB, true);
    real t = fabs(fracPartOfGoal - modf(sumB, &dummy)); //興味があるのは非常に近い場合だけだからこれでいい
    auto range = subsetSumOfA.equal_range(getKey(t));
    for (auto i = range.first; i != range.second; ++i) {
      int codeA = i->second->first;
      real sumA = i->second->second;
      real delta = fabs(fracPartOfGoal - modf(sumA, &dummy) - modf(sumB, &dummy));
      if (delta < minDelta) {
//#pragma omp critical
        {
          minDelta = delta;
          codeAforMinDelta = codeA;
          codeBforMinDelta = codeB;
          sumAforMinDelta = sumA;
          sumBforMinDelta = sumB;
        }
      }
    }
  }

  //整数部分を揃える
  real sum = sumAforMinDelta + sumBforMinDelta;
  minDelta = DELTA;
  int codeCforMinDelta = 0;
  for (uint codeC = 0; codeC < (1u << groupC.size()); ++codeC) {
    real delta = fabs(goal - sum - getSum(codeC, &groupC, false));
    if (delta < minDelta) {
      minDelta = delta;
      codeCforMinDelta = codeC;
    }
  }

  std::cout << setprecision(30) << goal << ": goal" << endl;
  auto solution1 = set<int>(); //ソート済みになる
  auto solution2 = set<int>();
  for (uint i = 0; i < groupA.size(); ++i) if (codeAforMinDelta >> i & 1) solution1.insert(a[i]);
  for (uint i = 0; i < groupB.size() - 1; ++i) if (codeBforMinDelta >> i & 1) solution1.insert(b[i]);
  for (uint i = 0; i < groupC.size(); ++i) if (codeCforMinDelta >> i & 1) solution1.insert(c[i]);
  set_difference(all.begin(), all.end(), solution1.begin(), solution1.end(), inserter(solution2, solution2.end()));
  printSolution(&solution1);
  printSolution(&solution2);

  clock_t finish = clock();
  real duration = real(finish - start) / CLOCKS_PER_SEC;
  cout << "Elapsed time: " << setprecision(3) << duration << " sec." << endl;
  return 0;
}

Ly9BcmUgVG95IFByb2JsZW1zIFVzZWZ1bD8KLy9pbiBTZWxlY3RlZCBQYXBlcnMgb24gQ29tcHV0ZXIgU2NpZW5jZSBieSBLbnV0aCAocC4xNzIpCgojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPHVub3JkZXJlZF9tYXA+IC8vIGZhc3RlciB0aGFuIG1hcAojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8Y3RpbWU+CiNkZWZpbmUgU1FSVCBzcXJ0bAp0eXBlZGVmIGxvbmcgZG91YmxlIHJlYWw7Ci8vI2RlZmluZSBTUVJUIHNxcnQKLy90eXBlZGVmIGRvdWJsZSByZWFsOwp0eXBlZGVmIHVuc2lnbmVkIGludCB1aW50Owp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgcmVhbCBERUxUQSA9IDEwMDAuOwpjb25zdCB1aW50IE4gPSA1MDsKY29uc3QgdWludCBzaXplQSA9IDIwOwoKaW50IGdldEtleShyZWFsIHgpCnsKICByZXR1cm4gc3RhdGljX2Nhc3Q8aW50PigoeCAtIGZsb29yKHgpKSAqIDFlOCk7Cn0KCnJlYWwgZ2V0U3VtKHVpbnQgY29kZSwgdmVjdG9yPHJlYWw+KiBncm91cCwgYm9vbCBpZ25vcmVMYXN0KQp7CiAgcmVhbCBzdW0gPSAwOwogIHVpbnQgc2l6ZSA9IGdyb3VwLT5zaXplKCk7CiAgaWYgKGlnbm9yZUxhc3QpIC0tc2l6ZTsKICBmb3IgKHVpbnQgaSA9IDA7IGkgPCBzaXplOyArK2kpIGlmIChjb2RlID4+IGkgJiAxKSBzdW0gKz0gKCpncm91cClbaV07CiAgcmV0dXJuIHN1bTsKfQoKdm9pZCBwcmludFNvbHV0aW9uKHNldDxpbnQ+KiBzb2x1dGlvbikKewogIHJlYWwgc3VtID0gMDsKICBzdHJpbmdzdHJlYW0gc3M7CiAgZm9yIChhdXRvIGkgOiAqc29sdXRpb24pIHsKICAgIHN1bSArPSBTUVJUKGkpOwogICAgc3MgPDwgaSA8PCAiLCI7CiAgfQogIHN0cmluZyBzdHIgPSBzcy5zdHIoKTsKICBjb3V0IDw8IHNldHByZWNpc2lvbigzMCkgPDwgc3VtIDw8ICI6IHsiIDw8IHN0ci5zdWJzdHIoMCwgc3RyLnNpemUoKS0xKSA8PCAifSIgPDwgZW5kbDsKfQoKaW50IG1haW4oKQp7CiAgYXV0byBzdGFydCA9IGNsb2NrKCk7CgogIHJlYWwgZHVtbXk7CiAgcmVhbCBnb2FsID0gMDsKICB2ZWN0b3I8aW50PiBhbGwsIGEsIGIsIGM7CiAgdmVjdG9yPHJlYWw+IGdyb3VwQSwgZ3JvdXBCLCBncm91cEM7IC8v5bmz5pa55qC544KS6KiI566X44GX44Gm44GK44GPCiAgZm9yICh1aW50IGkgPSAxOyBpIDw9IE47ICsraSkgewogICAgYWxsLnB1c2hfYmFjayhpKTsgLy97MSwgMiwgLi4uLCA1MH0KICAgIHJlYWwgdCA9IFNRUlQoaSk7CiAgICBnb2FsICs9IHQ7CiAgICBpZiAodCA9PSBmbG9vcih0KSkgewogICAgICBjLnB1c2hfYmFjayhpKTsgLy97MSwgNCwgOSwgMTYsIDI1LCAzNiwgNDl9CiAgICAgIGdyb3VwQy5wdXNoX2JhY2sodCk7CiAgICB9CiAgICBlbHNlIGlmIChhLnNpemUoKSA8IHNpemVBKSB7CiAgICAgIGEucHVzaF9iYWNrKGkpOyAvL3syLCAzLCA1LCA2LCA3LCA4LCAxMCwgMTEsIDEyLCAxMywuLi4KICAgICAgZ3JvdXBBLnB1c2hfYmFjayh0KTsKICAgIH0KICAgIGVsc2UgewogICAgICBiLnB1c2hfYmFjayhpKTsKICAgICAgZ3JvdXBCLnB1c2hfYmFjayh0KTsKICAgIH0KICB9CiAgZ29hbCAvPSAyLjsKICByZWFsIGZyYWNQYXJ0T2ZHb2FsID0gbW9kZihnb2FsLCAmZHVtbXkpOwoKICAvL2Hjga5zdWJzZXQgc3Vt44KS6KiI566X44GX44CB6KiY5oa244GZ44KLCiAgdW5vcmRlcmVkX211bHRpbWFwPGludCwgcGFpcjxpbnQsIHJlYWw+KiA+IHN1YnNldFN1bU9mQTsgLy/jgq3jg7zvvJrmpoLmlbDjgIHlgKTvvJpjb2RlQeOBqOWSjOOBruODmuOCogogIGZvciAodWludCBjb2RlQSA9IDA7IGNvZGVBIDwgKDF1IDw8IGdyb3VwQS5zaXplKCkpOyArK2NvZGVBKSB7CiAgICByZWFsIHN1bUEgPSBnZXRTdW0oY29kZUEsICZncm91cEEsIGZhbHNlKTsKICAgIGludCBrZXkgPSBnZXRLZXkoc3VtQSk7CiAgICBhdXRvIHAgPSBuZXcgcGFpcjxpbnQsIHJlYWw+KGNvZGVBLCBzdW1BKTsKICAgIHN1YnNldFN1bU9mQS5pbnNlcnQocGFpcjxpbnQsIHBhaXI8aW50LCByZWFsPiogPihrZXksIHApKTsKICB9CgogIC8vYuOBrnN1YnNldCBzdW3jgpLoqIjnrpfjgZnjgosKICByZWFsIG1pbkRlbHRhID0gREVMVEE7CiAgaW50IGNvZGVBZm9yTWluRGVsdGEgPSAwLCBjb2RlQmZvck1pbkRlbHRhID0gMDsKICByZWFsIHN1bUFmb3JNaW5EZWx0YSA9IDAsIHN1bUJmb3JNaW5EZWx0YSA9IDA7Ci8vI3ByYWdtYSBvbXAgcGFyYWxsZWwKICBmb3IgKHVpbnQgY29kZUIgPSAwOyBjb2RlQiA8ICgxdSA8PCAoZ3JvdXBCLnNpemUoKSAtIDEpKTsgKytjb2RlQikgeyAvL2Ljga4x44Gk44Gu6KaB57Sg44Gv5rG644KB44Gm44GK44GE44Gm44KI44GECiAgICByZWFsIHN1bUIgPSBnZXRTdW0oY29kZUIsICZncm91cEIsIHRydWUpOwogICAgcmVhbCB0ID0gZmFicyhmcmFjUGFydE9mR29hbCAtIG1vZGYoc3VtQiwgJmR1bW15KSk7IC8v6IiI5ZGz44GM44GC44KL44Gu44Gv6Z2e5bi444Gr6L+R44GE5aC05ZCI44Gg44GR44Gg44GL44KJ44GT44KM44Gn44GE44GECiAgICBhdXRvIHJhbmdlID0gc3Vic2V0U3VtT2ZBLmVxdWFsX3JhbmdlKGdldEtleSh0KSk7CiAgICBmb3IgKGF1dG8gaSA9IHJhbmdlLmZpcnN0OyBpICE9IHJhbmdlLnNlY29uZDsgKytpKSB7CiAgICAgIGludCBjb2RlQSA9IGktPnNlY29uZC0+Zmlyc3Q7CiAgICAgIHJlYWwgc3VtQSA9IGktPnNlY29uZC0+c2Vjb25kOwogICAgICByZWFsIGRlbHRhID0gZmFicyhmcmFjUGFydE9mR29hbCAtIG1vZGYoc3VtQSwgJmR1bW15KSAtIG1vZGYoc3VtQiwgJmR1bW15KSk7CiAgICAgIGlmIChkZWx0YSA8IG1pbkRlbHRhKSB7Ci8vI3ByYWdtYSBvbXAgY3JpdGljYWwKICAgICAgICB7CiAgICAgICAgICBtaW5EZWx0YSA9IGRlbHRhOwogICAgICAgICAgY29kZUFmb3JNaW5EZWx0YSA9IGNvZGVBOwogICAgICAgICAgY29kZUJmb3JNaW5EZWx0YSA9IGNvZGVCOwogICAgICAgICAgc3VtQWZvck1pbkRlbHRhID0gc3VtQTsKICAgICAgICAgIHN1bUJmb3JNaW5EZWx0YSA9IHN1bUI7CiAgICAgICAgfQogICAgICB9CiAgICB9CiAgfQoKICAvL+aVtOaVsOmDqOWIhuOCkuaPg+OBiOOCiwogIHJlYWwgc3VtID0gc3VtQWZvck1pbkRlbHRhICsgc3VtQmZvck1pbkRlbHRhOwogIG1pbkRlbHRhID0gREVMVEE7CiAgaW50IGNvZGVDZm9yTWluRGVsdGEgPSAwOwogIGZvciAodWludCBjb2RlQyA9IDA7IGNvZGVDIDwgKDF1IDw8IGdyb3VwQy5zaXplKCkpOyArK2NvZGVDKSB7CiAgICByZWFsIGRlbHRhID0gZmFicyhnb2FsIC0gc3VtIC0gZ2V0U3VtKGNvZGVDLCAmZ3JvdXBDLCBmYWxzZSkpOwogICAgaWYgKGRlbHRhIDwgbWluRGVsdGEpIHsKICAgICAgbWluRGVsdGEgPSBkZWx0YTsKICAgICAgY29kZUNmb3JNaW5EZWx0YSA9IGNvZGVDOwogICAgfQogIH0KCiAgc3RkOjpjb3V0IDw8IHNldHByZWNpc2lvbigzMCkgPDwgZ29hbCA8PCAiOiBnb2FsIiA8PCBlbmRsOwogIGF1dG8gc29sdXRpb24xID0gc2V0PGludD4oKTsgLy/jgr3jg7zjg4jmuIjjgb/jgavjgarjgosKICBhdXRvIHNvbHV0aW9uMiA9IHNldDxpbnQ+KCk7CiAgZm9yICh1aW50IGkgPSAwOyBpIDwgZ3JvdXBBLnNpemUoKTsgKytpKSBpZiAoY29kZUFmb3JNaW5EZWx0YSA+PiBpICYgMSkgc29sdXRpb24xLmluc2VydChhW2ldKTsKICBmb3IgKHVpbnQgaSA9IDA7IGkgPCBncm91cEIuc2l6ZSgpIC0gMTsgKytpKSBpZiAoY29kZUJmb3JNaW5EZWx0YSA+PiBpICYgMSkgc29sdXRpb24xLmluc2VydChiW2ldKTsKICBmb3IgKHVpbnQgaSA9IDA7IGkgPCBncm91cEMuc2l6ZSgpOyArK2kpIGlmIChjb2RlQ2Zvck1pbkRlbHRhID4+IGkgJiAxKSBzb2x1dGlvbjEuaW5zZXJ0KGNbaV0pOwogIHNldF9kaWZmZXJlbmNlKGFsbC5iZWdpbigpLCBhbGwuZW5kKCksIHNvbHV0aW9uMS5iZWdpbigpLCBzb2x1dGlvbjEuZW5kKCksIGluc2VydGVyKHNvbHV0aW9uMiwgc29sdXRpb24yLmVuZCgpKSk7CiAgcHJpbnRTb2x1dGlvbigmc29sdXRpb24xKTsKICBwcmludFNvbHV0aW9uKCZzb2x1dGlvbjIpOwoKICBjbG9ja190IGZpbmlzaCA9IGNsb2NrKCk7CiAgcmVhbCBkdXJhdGlvbiA9IHJlYWwoZmluaXNoIC0gc3RhcnQpIC8gQ0xPQ0tTX1BFUl9TRUM7CiAgY291dCA8PCAiRWxhcHNlZCB0aW1lOiAiIDw8IHNldHByZWNpc2lvbigzKSA8PCBkdXJhdGlvbiA8PCAiIHNlYy4iIDw8IGVuZGw7CiAgcmV0dXJuIDA7Cn0=