Arduino.ru

Можно придумать задачу на принципы работы со входящими и исходящими сигналами, без внешних источников и приёмников, т.е с имитацией. Программно на ардуино это осуществимо.

ПС: чёт у меня "очучение", что у меня часовой пояс ближе к Москве, чем у остальных.

Честно говоря, даже предложенная Петровичем задача вызвала у меня, минимум, одну отрицательную эмоцию: задачи подобного типа должны брать входные данные из файла, а не из включенного в код массива. Так что "портирование" данной задачи на Ардуино не обошлось без явных потерь.

А в этой связи родилась мысль: а так ли уж необходимо, чтобы задачи на программирование были непосредственно адаптированы к Ардуино? Может, интерес вызовет и задачи, ориентированные на ПК?

Ну и по поводу Ардуино: здесь, безусловно, интерес представляют не только (а, возможно, и не столько) задачи на программирование, но и задачи на умелое использование аппаратных ресурсов контроллера. И ограничение "без внешних цепей" тоже представляется чрезмерно жестким: вряд ли требование наличия самой стандартной периферии: нескольких кнопок, светодиодов, потенциометров или дисплея 1602 может вызвать трудности для обитателей данного форума.

Для меня необходимость выполнить задачу на заданной платформе составила главную изюминку конкурса. Это форум ардуино и потому я за эадачки для Мк, а не для пк

Тоже согласен, у каждого ардунщика должен быть минимальный набор, это тоже залог для будущих конкурсов.

Ну, изюминка здесь исключительно в ограничении на объем RAM. В принципе, тоже важно. Вопрос: будет ли экономное использование памяти учитываться при оценке.

Ну чё там, чё с результатом конкурса? Я уже почти согласен приз не получать, если выиграю, главное что там по результату.

Ну или вариант кода ЕвгенийП увидеть.

Итак, коллеги, ещё раз прошу извинения за задержку, но таки приступаем к подведению итогов.

Тема сильно замусорена, потому я боюсь, что-то пропустить или взять не последние версии. Тем более, заявления типа

тоже однозначности не добавляют.

Поэтому, пока я тут готовлю тесты и мучаю коды, проверьте. пожалуйста, правильные ли версии я взял. 

Сейчас я работаю с такими версиями:

AndreyD - из поста #289

kolyn - из поста #288

b707 - из поста #274.

Если я кого-то пропустил (был ещё участник) или у кого-то взял не последнюю версию, пожалуйста скажите!

у меня была одна версия, эта правильная

Предварительные итоги.

Коллеги, удалось посмотреть все три программы, присланные для участия в конкурсе. Буду смотреть ещё, работа не закончена, но пока могу сказать следующее:

Из трех программ пока не удалось получить неверный результат только от программы от Kolyn (но я не оставляю попыток :-))). Так что у нас есть лидер! У остальных, к сожалению неверные результаты проскакивают. Чтобы не быть голословным:

AndreyD, проверьте на вот таком тесте:

static Spanner spanners[] = {
		{8, 10, 8700},
		{15, 9, 8196},
		{12, 16, 6869},
		{11, 8, 3652},
		{9, 12, 7345},
		{11, 10, 3749},
		{10, 9, 7685},
		{8, 10, 2293},
		{15, 9, 8794},
		{15, 12, 4720},
		{14, 9, 6164},
		{16, 9, 2700},
		{16, 8, 9370}
};



//////////// ВАШЕ РЕШЕНИЕ ///////////////

2. 12-16: 68 руб. 69 коп.
4. 11-8: 36 руб. 52 коп.
6. 8-10: 22 руб. 93 коп.
7. 15-12: 47 руб. 20 коп.
8. 14-9: 61 руб. 64 коп.
Стоимость набора: 236 руб. 98 коп.

//////////// БОЛЕЕ ДЕШЕВОЕ РЕШЕНИЕ ///////////////

1. 8-10: 22 руб. 93 коп.
2. 16-9: 27 руб. 0 коп.
3. 11-8: 36 руб. 52 коп.
5. 15-12: 47 руб. 20 коп.
11. 14-9: 61 руб. 64 коп.
Стоимость набора: 195 руб. 29 коп.

B707, посмотрите на вот такой тест. Решение получается пустым:

static Spanner spanners[] = {
		{11, 10, 3177},
		{14, 15, 6129},
		{12, 15, 3119},
		{12, 11, 3522},
		{10, 8, 5770},
		{14, 11, 8367},
		{8, 14, 6532}
};

Это не единственные тесты, на которых работает неверно, но я предполагаю, что все они связаны с одной и той же ошибкой, потому остальные не выкладываю. Если это поможет в поиске ошибки - могу выложить.

Работа продолжается!

static Spanner spanners[] = {
		{8, 10, 8700},
		{15, 9, 8196},
		{12, 16, 6869},
		{11, 8, 3652},
		{9, 12, 7345},
		{11, 10, 3749},
		{10, 9, 7685},
		{8, 10, 2293},
		{15, 9, 8794},
		{15, 12, 4720},
		{14, 9, 6164},
		{16, 9, 2700},
		{16, 8, 9370}
};



//////////// ВАШЕ РЕШЕНИЕ ///////////////

2. 12-16: 68 руб. 69 коп.
4. 11-8: 36 руб. 52 коп.
6. 8-10: 22 руб. 93 коп.
7. 15-12: 47 руб. 20 коп.
8. 14-9: 61 руб. 64 коп.
Стоимость набора: 236 руб. 98 коп.

//////////// БОЛЕЕ ДЕШЕВОЕ РЕШЕНИЕ ///////////////

1. 8-10: 22 руб. 93 коп.
2. 16-9: 27 руб. 0 коп.
3. 11-8: 36 руб. 52 коп.
5. 15-12: 47 руб. 20 коп.
11. 14-9: 61 руб. 64 коп.
Стоимость набора: 195 руб. 29 коп.

Признаю поражение.

Ошибка в строках 151-205 моего кода (блок // Удаляем более дорогие ключи с одним оставшимся размером, а если размера только два, второй ключ добовляем в результирующий набор, помечая размеры на удаление из этого ключа.)

Не до конца продумал логику.

Отсев дублей и последующий перебор сочетанями без повторений, видимо, более правильное решение. Так что, думаю, что у Kolyn все ответы будут правильными.

Попробуйте, пожалуйста, вот такой вариант на наборах, которые выдавали ошибочный ответ:

//  Тип данных для хранения ключа
struct Spanner : public Printable {
  uint32_t price;// цена в копейках
  uint8_t size1;  // размер 1
  uint8_t size2;  // размер 2
  bool included; // если true, то включается в результирующий набор или дубли

Spanner(const uint8_t s1, const uint8_t s2, const uint32_t p, const bool ini = false) 
    :  price(p), size1(s1), size2(s2), included(ini) {}
  
  size_t printTo(Print & p) const {
    size_t res = p.print(size1);
    res += p.print(F("-"));
    res += p.print(size2);
    res += p.print(F(": "));
    res += printPrice(p, price);
    return res;
  }
  
  static size_t printPrice(Print & p, const uint32_t priceCop) {
    size_t res = p.print(priceCop / 100);
    res += p.print(F(" руб. "));
    res += p.print(priceCop % 100);
    res += p.print(F(" коп."));
    return res;
  }
};

//  Массив всех ключей
// Ключей в массиве не больше 100
// Размеры в одном ключе целочисленные, не равны 0, не равны между собой, и каждый не больше 255
// При наличии пресекающихся по размерам ключей в кол-ве больше 30 вычисления могут занять длительное время
static Spanner spanners[] = {

    {8, 10, 8700},
    {15, 9, 8196},
    {12, 16, 6869},
    {11, 8, 3652},
    {9, 12, 7345},
    {11, 10, 3749},
    {10, 9, 7685},
    {8, 10, 2293},
    {15, 9, 8794},
    {15, 12, 4720},
    {14, 9, 6164},
    {16, 9, 2700},
    {16, 8, 9370}

};
static constexpr uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);

uint8_t  sizes[totalSpanners * 2], cSizes[totalSpanners * 2];  

Spanner tempS[] = {{0,0,0,0}};
bool flag1=0, flag2=0, flag3=0; 
uint8_t totalSpanners1=0, allSizes=0;


// Функция перебора сочетаний без повторений
bool nextSet(uint8_t *indexKeys, int16_t n, int16_t m) {
  for (int16_t i = m - 1; i >= 0; i--) {
    if (indexKeys[i] < n - m + i) {
      indexKeys[i]++;
      for (int16_t j = i + 1; j < m; j++)
        indexKeys[j] = indexKeys[j - 1] + 1;
      return 1;
    }
  }
  return 0;
}

void doCalculations(void) {
  memset(sizes, 0, sizeof(sizes[0]) * (totalSpanners * 2)); // Обнуление массива размеров.
  memset(cSizes, 0, sizeof(cSizes[0]) * (totalSpanners * 2)); // Обнуление массива кол-ва одинаковых размеров.

  // Поиск более дорогих дублей и удаление их сдвигом из массива структур
  totalSpanners1 = totalSpanners;
  for (uint8_t i=0; i < totalSpanners1; i++) 
    for (uint8_t j=i+1; j < totalSpanners1; j++) 
      if ((((spanners[i].size1 == spanners[j].size1) && (spanners[i].size2 == spanners[j].size2)) || 
          ((spanners[i].size1 == spanners[j].size2) && (spanners[i].size2 == spanners[j].size1)))) {
        if (spanners[i].price >= spanners[j].price) {
          for (uint8_t k = i; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          i--;
        } else {
          for (uint8_t k = j; k < totalSpanners1 - 1; k++)
            spanners[k] = spanners[k + 1];
          j--;
        }
      totalSpanners1--; 
      }

  // Если все дубли выводим результат с одним ключём
  if (totalSpanners1 == 1) {spanners[0].included = 1; return;}

  // Поиск всех размеров ключей и вычисление кол-ва каждого размера
  for (uint8_t i = 0; i < totalSpanners1; i++) {
    for (uint8_t j=0; j < allSizes; j++) {
      if (sizes[j] == spanners[i].size1) {flag1=1; cSizes[j]++;}
      if (sizes[j] == spanners[i].size2) {flag2=1; cSizes[j]++;}
    }
      if (!flag1) {sizes[allSizes] = spanners[i].size1; allSizes++;} else flag1=0; 
      if (!flag2) {sizes[allSizes] = spanners[i].size2; allSizes++;} else flag2=0;
  }

  // Добавление ключей с одним размером в результирующий набор
  for (uint8_t i = 0; i < allSizes; i++) 
     if (cSizes[i] == 0)  
      for (uint8_t j=0; j < totalSpanners1; j++) { 
        if (spanners[j].included) continue;
          if (sizes[i] == spanners[j].size1 || sizes[i] == spanners[j].size2) 
            spanners[j].included = 1;
      }
       
  // Пометка вторых размеров из уже выбранных ключей на удаление
  for (uint8_t i=0; i < totalSpanners1; i++)
     if (spanners[i].included)
       for (uint8_t j = 0; j < allSizes; j++) 
         if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) cSizes[j] = 0;

    // Удаление размеров которые уже есть в выбраных ключах
    for (uint8_t i = 0; i < allSizes; i++)
      if (cSizes[i] == 0) {
        for (uint8_t j = i; j < allSizes - 1; j++) 
          {sizes[j] = sizes[j+1]; cSizes[j] = cSizes[j+1];}
        allSizes--; i--;
      }

    // Удаление ключей у которых оба размера совпадает с размерами уже выбранных ключей.
    for (uint8_t i = 0; i < totalSpanners1; i++) {
      if (spanners[i].included) continue;
      flag1=0;
      for (uint8_t j = 0; j < allSizes; j++)
        if (sizes[j] == spanners[i].size1 || sizes[j] == spanners[i].size2) flag1=1;
      if (!flag1) {
        for (uint8_t k = i; k < totalSpanners1 - 1; k++) 
          spanners[k] = spanners[k + 1];
        totalSpanners1--; i--;
        spanners[totalSpanners1].included = 0;
      }
    }


  // Убираем уже выбранные ключи в конец массива
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
      if (spanners[j].included > spanners[j+1].included) {
        tempS[0] = spanners[j];
        spanners[j] = spanners[j + 1];
        spanners[j + 1] = tempS[0];
      }
  
  // Считаем оставшиеся ключи.
  for (uint8_t i = 0; i < totalSpanners1; i++)
    if (spanners[i].included == 1) totalSpanners1 = i;

  //Сортировка оставшихся ключей по цене от большей к меньшей
  for (uint8_t i = 0; i < totalSpanners1; i++)
    for (uint8_t j = 0; j < totalSpanners1 - 1; j++)
    if (spanners[j].price < spanners[j+1].price) {
      tempS[0] = spanners[j];
      spanners[j] = spanners[j + 1];
      spanners[j + 1] = tempS[0];
    }

  bool stopElem=0;
  int16_t n=totalSpanners1;
  uint8_t *indexKeys, rezIndexKeys[n], rezM=0, elem=0;
  indexKeys = new int8_t[n];
  uint64_t rezSumPrice = UINT64_MAX, sumPrice = 0;

  // перебор сочетаний индексов массива ключей
  // n - кол-во оставшихся не выбранных ключей
  // m - от половины оставшихся размеров до кол-ва не выбранных ключей
  for (int16_t m=round(((float)allSizes/2)); m <= n; m++) {
    for (int16_t i = 0; i < n; i++)
      indexKeys[i] = i;
    do {
      sumPrice = 0; flag1=1; 
      // Проверка, что сумма сочетания меньше суммы предыдущего выбранного сочетания
      for (int16_t i = 0; i < m; i++) {
        sumPrice = sumPrice + uint64_t(spanners[indexKeys[i]].price);
        if (sumPrice >= rezSumPrice) {flag1 = 0; break;}
      }
      if (flag1) {
        flag2=1;
        // Проверка наличия всех оставшихся размеров в сочетании
        for (uint8_t i=0; i < allSizes; i++) {
          for (uint8_t j=0; j < m; j++) {
            if ((spanners[indexKeys[j]].size1 == sizes[i]) ||  (spanners[indexKeys[j]].size2 == sizes[i])) break;
            if (j == m-1) 
              if ((spanners[indexKeys[j]].size1 != sizes[i]) &&  (spanners[indexKeys[j]].size2 != sizes[i]))
                flag2=0;
          }
          if (!flag2) break;
        }
      }
      // Если обе проверки пройдены сохраняем результат
      if (flag1 && flag2) {
        rezSumPrice = sumPrice;
        rezM = m;
        for (uint8_t j = 0; j < m; j++) 
          rezIndexKeys[j] = indexKeys[j];
      }
    } while (nextSet(indexKeys, n, m));
  } 
    // Добавляем ключи выбранные на основе перебора в результирующий набор
    for (uint8_t i = 0; i < rezM; i++) {
      spanners[rezIndexKeys[i]].included = 1;
    }
}

void printResults(void) {
  Serial.println(F("Ключи"));
  uint32_t total = 0;
  for (uint8_t i = 0; i < totalSpanners; i++) {
    if (spanners[i].included) {
      Serial.print(i + 1);
      Serial.print(". ");
      Serial.println(spanners[i]);
      total += spanners[i].price;
    }
  }
  Serial.print(F("Стоимость набора: "));
  Spanner::printPrice(Serial, total);
  Serial.println();
}

void setup(void) {
  Serial.begin(9600);
  const uint32_t start = millis();
  if (totalSpanners > 100) {Serial.println(F("Колличество ключей больше 100. Уменьшите их колличество.")); return;}
  doCalculations();
  const uint32_t duration = millis() - start;
  printResults();
  Serial.print(F("Время расчёта: "));
  Serial.print(duration);
  Serial.println(F(" миллисекунд"));
}

void loop(void) {}  

Имейте совесть! Не мешайте человеку подвести итоги конкурса - это большая работа.

Я же не говорю прямо сейчас, и ни в коем случае не требую прямо сейчас. Я же уже выбыл из кандидатов на победу.

static Spanner spanners[] = {
		{11, 10, 3177},
		{14, 15, 6129},
		{12, 15, 3119},
		{12, 11, 3522},
		{10, 8, 5770},
		{14, 11, 8367},
		{8, 14, 6532}
};

не надо, ошибку нашел сразу.

Правильный ответ:

=== Span selection ===
Span  10x11
Span  8x14
Span  12x15
Total value = 128.28
Calculation time = 2.320 ms

Обидно, что в версии, что закончил через 3 часа после закрытия турнира - этой ошибки нет.

Но тут уж ничего не попишешь. Выложил я на конкурс эту версию, поэтому что о других говорить.

Обидно конечно, столько ждать проверки - и вылететь на первом тесте :( ЭХХХ

пойду напьюсь

Попробуйте сами на вот этих пяти тестах. Для проверки результатов используйте любую из программ коллег - с этими пятью они обе справляются.

//
//	 Test # 9
	{
		{8, 10, 8700},
		{15, 9, 8196},
		{12, 16, 6869},
		{11, 8, 3652},
		{9, 12, 7345},
		{11, 10, 3749},
		{10, 9, 7685},
		{8, 10, 2293},
		{15, 9, 8794},
		{15, 12, 4720},
		{14, 9, 6164},
		{16, 9, 2700},
		{16, 8, 9370}
	},
//
//	 Test # 13
	{
		{8, 15, 5244},
		{8, 12, 8373},
		{14, 12, 9749},
		{9, 8, 5293},
		{11, 15, 7490},
		{15, 13, 2787},
		{13, 12, 5059},
		{12, 9, 2506},
		{9, 15, 7857},
		{9, 8, 3433},
		{8, 9, 8822},
		{10, 13, 5709},
		{11, 15, 6904}
	},
//
//	 Test # 21
	{
		{9, 11, 5634},
		{15, 16, 9009},
		{15, 11, 6572},
		{14, 11, 6608},
		{16, 8, 2941},
		{11, 10, 7810},
		{15, 12, 8378},
		{15, 9, 4976},
		{9, 15, 2728},
		{12, 10, 6518},
		{16, 13, 7605},
		{11, 14, 6074},
		{15, 9, 4811}
	},
//
//	 Test # 31
	{
		{12, 9, 9133},
		{14, 9, 7136},
		{12, 13, 1794},
		{13, 12, 7370},
		{10, 16, 4472},
		{13, 15, 3547},
		{15, 8, 5149},
		{15, 9, 8851},
		{9, 13, 2405},
		{9, 12, 9134},
		{11, 12, 7756},
		{15, 11, 6702},
		{12, 11, 2997}
	},
//
//	 Test # 47
	{
		{15, 13, 6927},
		{13, 14, 9511},
		{13, 9, 6512},
		{10, 11, 9997},
		{10, 15, 6969},
		{8, 15, 5574},
		{12, 11, 5604},
		{8, 11, 2422},
		{10, 13, 8607},
		{10, 16, 5706},
		{11, 10, 5120},
		{14, 13, 3363},
		{13, 11, 3537}
	},

Вы ж вроде, нас с дедом в этом деле никогда не поддерживали!

это потому что у меня повода серьезного не было :)

Мне на эту тему очень картинко нравиццо

начинать надо было с той моей задачи про бочку, кою решил (почти) только один человек на форуме (кроме дракулы, но я его решение даже понять не в состоянии, не то, что проверить) :-)))

Для конкурса крайне важно, чтобы Организатор и Жюри пользовались безусловным авторитетом в данной области... иначе итогом будет просто срач. как и сложилось в твоем случае.

Да приведённый мной код в сообщении #360 считает эти тесты правильно, НО проигрывает по времени коду  kolyn , т.е. без правильной реализации моего пятого пункта словесного алгоритма я бы всё равно не выиграл.

Пятый пункт:

Далее могут присутствовать ключи, у которых один размер исключен, можно сравнить его стоимость с остальными ключами с таким же размером и если его цена больше то исключить его. При этом, если кол-во ключей с этим размером был равен 2, то более дешёвый ключ становиться уникальным. А его второй размер исключается из дальнейшего перебора.

Ну, что коллеги, давайте подводить итоги.

Обработка результатов производилась в два этапа. На первом этапе я просто смотрел на программы и запускал их, чтобы проверить свои предположения об их поведении (правильно ли я их понимаю). На этом этапе обнаружилось, что две из трёх присланных программ содержат ошибки, которые проявляются на некоторых тестах.

Ну, как бы с победителем стало всё ясно, но это формальная сторона вопроса. В реальности же, ошибки мне показались непринципиальными (легко исправимыми), а идеи, заложенные в программах весьма интересными, поэтому я решил продолжить исследование (считая, что ошибки как бы исправлены) и выяснить вопросы скорости, тем более, что тем, кто предложит вариант быстрее моего, был обещать отдельный приз.

Последнее (предложение приза) было вполне реальным и я надеялся, что его кто-то выиграет, т.к. изначально я не планировал писать свою программу "на все деньги", т.е. добиваться того, чтобы она была как можно более эффективной. Вместо этого я планировал использовать только очевидные и бесспорные оптимизации и стандартные, "вездеупотребительные" методы. Т.е. я хотел написать учебный материал по общим методам решения задач такого рода и не более того. Такая программа заведомо должна проигрывать специализированным программам, использующим частные методы "под задачу". Её ценность в демонстрации общих методов, которые применимы для всех задач. Я рассчитывал, что кто-нибудь обязательно напишет более быстрое решение. Считаю, что в действительности так и получилось, несмотря на то, что формально это не так (см. ниже).

Таким образом, на втором этапе я нагенерил кучу случайных тестов, а именно - девяносто  тестов с семью ключами, пятьдесят тестов с тринадцатью ключами и тридцать два теста с семнадцатью ключами и прогнал через эти 172 теста все программы, включая и свою - внеконкурсную.

Все использованные тесты приведены ниже (повторяю, они получились путём генерации псевдослучайных чисел).

Тесты с 7 ключами

static Spanner allTheTests[totalTests][7] = { 
//
//	 Test # 1
	{
		{16, 14, 9431},
		{16, 8, 7776},
		{8, 12, 8290},
		{9, 16, 6282},
		{13, 15, 4260},
		{14, 11, 7357},
		{15, 13, 9957}
	},
//
//	 Test # 2
	{
		{9, 13, 4648},
		{16, 13, 9907},
		{13, 14, 6005},
		{14, 11, 4964},
		{8, 14, 7325},
		{10, 16, 4272},
		{14, 13, 1993}
	},
//
//	 Test # 3
	{
		{11, 14, 9017},
		{11, 15, 3963},
		{10, 12, 7654},
		{9, 15, 6947},
		{13, 9, 4318},
		{9, 10, 3064},
		{16, 8, 1560}
	},
//
//	 Test # 4
	{
		{9, 12, 3959},
		{11, 8, 3527},
		{14, 11, 8520},
		{9, 10, 7328},
		{12, 10, 6730},
		{14, 10, 3918},
		{12, 13, 5089}
	},
//
//	 Test # 5
	{
		{16, 15, 6895},
		{10, 16, 9018},
		{16, 13, 3879},
		{9, 8, 3853},
		{9, 14, 2905},
		{8, 11, 4458},
		{16, 12, 7006}
	},
//
//	 Test # 6
	{
		{8, 12, 2489},
		{9, 16, 4009},
		{13, 8, 4862},
		{11, 13, 3439},
		{10, 15, 4757},
		{16, 12, 8643},
		{15, 13, 6378}
	},
//
//	 Test # 7
	{
		{8, 10, 1996},
		{12, 9, 8420},
		{14, 12, 8665},
		{16, 15, 2908},
		{10, 16, 2495},
		{9, 13, 9444},
		{13, 15, 6352}
	},
//
//	 Test # 8
	{
		{13, 15, 3007},
		{10, 11, 5670},
		{14, 10, 7269},
		{10, 8, 5616},
		{10, 12, 1820},
		{15, 10, 5161},
		{8, 16, 8007}
	},
//
//	 Test # 9
	{
		{11, 13, 3069},
		{9, 8, 7444},
		{10, 9, 9407},
		{10, 15, 6004},
		{14, 12, 2785},
		{10, 14, 2953},
		{15, 9, 4158}
	},
//
//	 Test # 10
	{
		{11, 8, 1664},
		{8, 10, 2884},
		{8, 10, 4046},
		{10, 9, 4310},
		{13, 14, 3165},
		{11, 16, 5772},
		{12, 16, 6180}
	},
//
//	 Test # 11
	{
		{15, 12, 5123},
		{12, 9, 8665},
		{14, 16, 6886},
		{13, 8, 2889},
		{9, 8, 7964},
		{12, 8, 7936},
		{8, 10, 6136}
	},
//
//	 Test # 12
	{
		{12, 15, 7841},
		{12, 10, 2443},
		{9, 8, 7749},
		{13, 12, 5214},
		{14, 13, 5139},
		{9, 14, 8542},
		{16, 12, 8088}
	},
//
//	 Test # 13
	{
		{14, 12, 3156},
		{8, 9, 6932},
		{16, 13, 6121},
		{9, 13, 4597},
		{14, 13, 9865},
		{11, 16, 8675},
		{11, 9, 9866}
	},
//
//	 Test # 14
	{
		{9, 14, 5023},
		{9, 14, 7900},
		{13, 16, 5041},
		{14, 15, 8689},
		{16, 8, 5506},
		{13, 11, 7497},
		{13, 14, 3306}
	},
//
//	 Test # 15
	{
		{9, 12, 7130},
		{10, 13, 5377},
		{11, 13, 2611},
		{12, 13, 9658},
		{8, 12, 3025},
		{9, 10, 4306},
		{13, 11, 9365}
	},
//
//	 Test # 16
	{
		{12, 10, 6364},
		{10, 9, 6389},
		{8, 12, 4006},
		{10, 11, 2471},
		{11, 14, 5487},
		{16, 13, 5911},
		{11, 14, 7965}
	},
//
//	 Test # 17
	{
		{8, 10, 4996},
		{9, 10, 5753},
		{12, 8, 5327},
		{14, 16, 9624},
		{12, 13, 1544},
		{14, 13, 9238},
		{11, 14, 3145}
	},
//
//	 Test # 18
	{
		{14, 16, 7351},
		{16, 14, 5495},
		{9, 14, 3026},
		{14, 13, 2919},
		{16, 10, 4142},
		{10, 16, 4725},
		{10, 12, 9164}
	},
//
//	 Test # 19
	{
		{13, 15, 6417},
		{14, 11, 8444},
		{14, 15, 9799},
		{16, 10, 3999},
		{14, 8, 1783},
		{13, 14, 3129},
		{9, 13, 7537}
	},
//
//	 Test # 20
	{
		{11, 8, 2353},
		{10, 11, 9156},
		{9, 16, 1610},
		{14, 15, 2366},
		{12, 13, 8434},
		{16, 14, 4156},
		{13, 11, 8778}
	},
//
//	 Test # 21
	{
		{12, 15, 8195},
		{15, 10, 4435},
		{14, 12, 2028},
		{14, 16, 1845},
		{12, 16, 4555},
		{11, 13, 9268},
		{10, 16, 7079}
	},
//
//	 Test # 22
	{
		{11, 10, 4962},
		{13, 15, 1547},
		{14, 13, 1534},
		{9, 16, 5904},
		{10, 9, 1519},
		{8, 13, 9074},
		{16, 8, 2854}
	},
//
//	 Test # 23
	{
		{8, 11, 3247},
		{11, 13, 7374},
		{16, 13, 5537},
		{12, 14, 9703},
		{10, 14, 4353},
		{13, 8, 2975},
		{11, 16, 4902}
	},
//
//	 Test # 24
	{
		{10, 11, 8713},
		{16, 9, 5166},
		{10, 16, 6884},
		{9, 15, 5960},
		{13, 9, 2903},
		{13, 14, 8174},
		{13, 9, 8100}
	},
//
//	 Test # 25
	{
		{15, 16, 2860},
		{9, 12, 2392},
		{16, 9, 1574},
		{12, 8, 7888},
		{12, 14, 2157},
		{8, 10, 3655},
		{15, 10, 2729}
	},
//
//	 Test # 26
	{
		{13, 16, 6891},
		{11, 15, 7362},
		{14, 10, 8414},
		{13, 16, 7555},
		{10, 14, 5304},
		{15, 8, 3101},
		{13, 10, 2361}
	},
//
//	 Test # 27
	{
		{13, 11, 1800},
		{8, 9, 3608},
		{13, 8, 5075},
		{8, 11, 3521},
		{16, 12, 8708},
		{15, 10, 8415},
		{16, 14, 2374}
	},
//
//	 Test # 28
	{
		{11, 15, 5769},
		{10, 15, 2877},
		{14, 12, 4467},
		{10, 13, 2508},
		{11, 14, 2577},
		{12, 15, 6553},
		{16, 14, 6696}
	},
//
//	 Test # 29
	{
		{14, 11, 7800},
		{14, 9, 7889},
		{16, 12, 4599},
		{11, 15, 6702},
		{14, 15, 6411},
		{10, 15, 7622},
		{8, 11, 7526}
	},
//
//	 Test # 30
	{
		{13, 8, 7933},
		{11, 13, 9914},
		{16, 12, 3501},
		{14, 11, 4755},
		{10, 9, 6061},
		{10, 15, 1752},
		{12, 9, 6118}
	},
//
//	 Test # 31
	{
		{12, 14, 3089},
		{8, 14, 4894},
		{15, 13, 8942},
		{14, 12, 4364},
		{13, 11, 2212},
		{11, 14, 5780},
		{15, 16, 7737}
	},
//
//	 Test # 32
	{
		{14, 16, 1800},
		{11, 8, 6833},
		{11, 10, 2661},
		{14, 15, 6924},
		{14, 13, 2213},
		{9, 11, 2159},
		{9, 15, 3796}
	},
//
//	 Test # 33
	{
		{15, 8, 5143},
		{14, 12, 3787},
		{9, 16, 5831},
		{13, 11, 3889},
		{11, 12, 9882},
		{14, 16, 6107},
		{9, 13, 8197}
	},
//
//	 Test # 34
	{
		{8, 9, 6950},
		{9, 13, 8258},
		{16, 15, 7013},
		{16, 13, 2879},
		{12, 8, 8703},
		{9, 12, 2250},
		{9, 16, 8078}
	},
//
//	 Test # 35
	{
		{13, 15, 7161},
		{10, 12, 4244},
		{14, 13, 4868},
		{13, 14, 6457},
		{13, 14, 7612},
		{15, 12, 7524},
		{10, 15, 1598}
	},
//
//	 Test # 36
	{
		{13, 12, 8412},
		{16, 13, 5684},
		{12, 16, 3816},
		{14, 15, 5213},
		{15, 13, 3424},
		{12, 16, 9108},
		{13, 10, 7882}
	},
//
//	 Test # 37
	{
		{11, 10, 3177},
		{14, 15, 6129},
		{12, 15, 3119},
		{12, 11, 3522},
		{10, 8, 5770},
		{14, 11, 8367},
		{8, 14, 6532}
	},
//
//	 Test # 38
	{
		{12, 14, 9936},
		{13, 8, 2396},
		{10, 12, 9817},
		{10, 16, 5206},
		{9, 12, 4977},
		{14, 15, 9777},
		{9, 8, 9710}
	},
//
//	 Test # 39
	{
		{13, 8, 9500},
		{15, 12, 6304},
		{12, 10, 9157},
		{11, 13, 8087},
		{8, 13, 8143},
		{11, 9, 4775},
		{11, 8, 9869}
	},
//
//	 Test # 40
	{
		{9, 13, 3792},
		{11, 12, 6821},
		{12, 11, 6200},
		{10, 8, 2152},
		{14, 15, 4195},
		{9, 14, 2344},
		{13, 8, 4868}
	},
//
//	 Test # 41
	{
		{10, 15, 2081},
		{11, 15, 7968},
		{13, 9, 5386},
		{11, 15, 9918},
		{12, 10, 7012},
		{8, 16, 2065},
		{15, 8, 2189}
	},
//
//	 Test # 42
	{
		{15, 12, 5048},
		{10, 15, 7793},
		{10, 9, 2410},
		{13, 16, 3410},
		{10, 8, 4544},
		{16, 13, 5282},
		{12, 15, 2757}
	},
//
//	 Test # 43
	{
		{12, 15, 5673},
		{12, 11, 4829},
		{16, 10, 4712},
		{9, 13, 8898},
		{16, 11, 4737},
		{9, 15, 7162},
		{11, 15, 3878}
	},
//
//	 Test # 44
	{
		{11, 14, 5513},
		{10, 13, 6684},
		{15, 8, 6123},
		{11, 8, 3834},
		{9, 11, 2388},
		{8, 15, 3685},
		{12, 16, 5604}
	},
//
//	 Test # 45
	{
		{14, 15, 4801},
		{10, 12, 2623},
		{15, 14, 6506},
		{12, 11, 6657},
		{12, 9, 4897},
		{8, 13, 6055},
		{13, 8, 7897}
	},
//
//	 Test # 46
	{
		{13, 16, 5342},
		{11, 8, 2733},
		{10, 11, 3215},
		{16, 13, 7819},
		{10, 13, 4357},
		{15, 8, 3665},
		{15, 11, 7283}
	},
//
//	 Test # 47
	{
		{14, 9, 9923},
		{15, 13, 4089},
		{8, 12, 8412},
		{16, 13, 4849},
		{11, 8, 2806},
		{16, 15, 1884},
		{16, 8, 1692}
	},
//
//	 Test # 48
	{
		{14, 13, 5917},
		{10, 12, 6584},
		{12, 11, 1637},
		{12, 8, 6825},
		{16, 8, 8809},
		{15, 8, 9644},
		{8, 9, 1609}
	},
//
//	 Test # 49
	{
		{12, 11, 6895},
		{12, 16, 9333},
		{10, 16, 2085},
		{8, 11, 7575},
		{8, 13, 7128},
		{12, 13, 5647},
		{9, 8, 3452}
	},
//
//	 Test # 50
	{
		{12, 14, 7092},
		{11, 15, 1553},
		{9, 15, 3365},
		{9, 16, 7291},
		{12, 14, 3751},
		{11, 15, 8542},
		{10, 8, 5708}
	},
//
//	 Test # 51
	{
		{9, 10, 2662},
		{12, 11, 7274},
		{14, 8, 2641},
		{8, 10, 5590},
		{12, 11, 6777},
		{11, 12, 4388},
		{8, 9, 8132}
	},
//
//	 Test # 52
	{
		{10, 14, 7839},
		{15, 14, 7739},
		{10, 12, 9888},
		{14, 15, 8868},
		{16, 11, 2374},
		{14, 8, 3065},
		{12, 9, 2661}
	},
//
//	 Test # 53
	{
		{16, 9, 8377},
		{14, 15, 4455},
		{10, 8, 2340},
		{12, 13, 1746},
		{10, 12, 5928},
		{11, 8, 6840},
		{15, 16, 9827}
	},
//
//	 Test # 54
	{
		{10, 11, 7395},
		{12, 13, 9133},
		{8, 15, 4952},
		{12, 13, 1654},
		{16, 8, 9522},
		{14, 12, 7590},
		{12, 11, 9653}
	},
//
//	 Test # 55
	{
		{8, 11, 7776},
		{12, 14, 4389},
		{12, 9, 3982},
		{14, 10, 9603},
		{11, 8, 7195},
		{9, 14, 1888},
		{8, 16, 4346}
	},
//
//	 Test # 56
	{
		{13, 10, 4164},
		{15, 9, 2340},
		{13, 9, 8062},
		{8, 13, 6850},
		{16, 15, 7059},
		{12, 14, 7792},
		{15, 10, 4088}
	},
//
//	 Test # 57
	{
		{9, 15, 2729},
		{9, 15, 3222},
		{11, 14, 7080},
		{10, 14, 3841},
		{12, 11, 2276},
		{13, 16, 4701},
		{8, 16, 4968}
	},
//
//	 Test # 58
	{
		{8, 12, 3498},
		{10, 16, 9509},
		{14, 15, 8195},
		{12, 16, 5713},
		{11, 15, 9591},
		{13, 11, 6345},
		{9, 16, 3939}
	},
//
//	 Test # 59
	{
		{8, 12, 1518},
		{10, 11, 5401},
		{14, 13, 8246},
		{16, 9, 5795},
		{16, 11, 8588},
		{9, 14, 3381},
		{11, 12, 4159}
	},
//
//	 Test # 60
	{
		{8, 11, 1961},
		{11, 13, 7761},
		{15, 16, 4402},
		{12, 11, 9693},
		{11, 16, 2695},
		{14, 12, 1812},
		{12, 14, 8047}
	},
//
//	 Test # 61
	{
		{11, 9, 5483},
		{8, 12, 4301},
		{11, 9, 6772},
		{12, 11, 7463},
		{8, 14, 7933},
		{9, 8, 4969},
		{16, 10, 3453}
	},
//
//	 Test # 62
	{
		{15, 11, 5283},
		{15, 8, 5647},
		{16, 15, 4292},
		{11, 13, 5081},
		{13, 10, 5840},
		{10, 8, 3182},
		{11, 8, 8504}
	},
//
//	 Test # 63
	{
		{9, 14, 2477},
		{10, 9, 3487},
		{13, 16, 1965},
		{15, 12, 7933},
		{8, 13, 7743},
		{11, 12, 6665},
		{13, 11, 7416}
	},
//
//	 Test # 64
	{
		{10, 12, 3994},
		{16, 12, 2259},
		{12, 10, 1806},
		{10, 11, 2487},
		{16, 13, 2669},
		{13, 8, 7649},
		{11, 16, 3864}
	},
//
//	 Test # 65
	{
		{10, 12, 8707},
		{8, 16, 7481},
		{10, 16, 9978},
		{9, 16, 9952},
		{15, 16, 6116},
		{9, 15, 8572},
		{14, 11, 1642}
	},
//
//	 Test # 66
	{
		{13, 9, 3733},
		{10, 9, 7992},
		{8, 12, 7026},
		{9, 14, 2177},
		{16, 12, 3755},
		{15, 14, 8925},
		{14, 15, 5248}
	},
//
//	 Test # 67
	{
		{11, 13, 3506},
		{14, 15, 5351},
		{14, 8, 6363},
		{8, 11, 1983},
		{15, 9, 4122},
		{8, 11, 8499},
		{9, 14, 9525}
	},
//
//	 Test # 68
	{
		{10, 11, 3260},
		{9, 16, 8786},
		{14, 9, 7176},
		{8, 11, 6679},
		{9, 13, 9128},
		{12, 14, 3277},
		{12, 8, 2887}
	},
//
//	 Test # 69
	{
		{13, 10, 5570},
		{16, 8, 9897},
		{11, 16, 1931},
		{10, 14, 4065},
		{9, 14, 8421},
		{16, 13, 4913},
		{9, 10, 9475}
	},
//
//	 Test # 70
	{
		{12, 16, 8642},
		{8, 12, 5076},
		{16, 15, 6069},
		{11, 15, 3334},
		{13, 12, 6435},
		{14, 11, 9538},
		{15, 11, 6953}
	},
//
//	 Test # 71
	{
		{13, 9, 3060},
		{14, 16, 8566},
		{16, 12, 6733},
		{11, 14, 2517},
		{14, 16, 5788},
		{11, 10, 3102},
		{13, 15, 2707}
	},
//
//	 Test # 72
	{
		{9, 14, 2284},
		{15, 8, 5562},
		{14, 10, 9912},
		{13, 12, 5634},
		{10, 16, 8711},
		{15, 8, 9556},
		{9, 13, 2865}
	},
//
//	 Test # 73
	{
		{16, 12, 5475},
		{11, 15, 8624},
		{16, 12, 6878},
		{9, 8, 2618},
		{10, 14, 8175},
		{13, 12, 6663},
		{8, 11, 7686}
	},
//
//	 Test # 74
	{
		{10, 9, 4310},
		{16, 8, 3634},
		{8, 9, 6115},
		{12, 16, 2979},
		{14, 8, 8119},
		{12, 16, 5634},
		{13, 14, 7608}
	},
//
//	 Test # 75
	{
		{8, 9, 6243},
		{9, 16, 7810},
		{14, 10, 8696},
		{16, 9, 2960},
		{11, 15, 2796},
		{8, 13, 5712},
		{13, 15, 3376}
	},
//
//	 Test # 76
	{
		{9, 13, 4943},
		{12, 13, 5002},
		{8, 11, 5027},
		{11, 8, 5731},
		{15, 8, 3591},
		{9, 11, 3588},
		{8, 9, 7990}
	},
//
//	 Test # 77
	{
		{13, 12, 4795},
		{10, 8, 5644},
		{10, 15, 3517},
		{15, 13, 2539},
		{9, 11, 8568},
		{10, 11, 4848},
		{8, 11, 4367}
	},
//
//	 Test # 78
	{
		{11, 12, 5877},
		{13, 9, 2878},
		{15, 12, 5628},
		{9, 13, 8686},
		{8, 11, 5799},
		{12, 16, 4556},
		{12, 14, 4394}
	},
//
//	 Test # 79
	{
		{14, 11, 1574},
		{11, 12, 7861},
		{11, 16, 5168},
		{11, 13, 3203},
		{15, 11, 5776},
		{12, 11, 2534},
		{12, 8, 7448}
	},
//
//	 Test # 80
	{
		{13, 12, 2535},
		{8, 14, 9549},
		{9, 10, 9546},
		{12, 16, 2405},
		{9, 10, 2323},
		{8, 14, 3051},
		{9, 14, 2050}
	},
//
//	 Test # 81
	{
		{15, 8, 3181},
		{16, 10, 7993},
		{13, 16, 6507},
		{13, 12, 1560},
		{9, 15, 3082},
		{10, 13, 4078},
		{9, 8, 1973}
	},
//
//	 Test # 82
	{
		{8, 14, 5149},
		{11, 8, 1611},
		{11, 8, 2386},
		{16, 15, 1648},
		{10, 12, 4761},
		{10, 8, 7372},
		{16, 9, 6232}
	},
//
//	 Test # 83
	{
		{12, 8, 8907},
		{14, 11, 3256},
		{11, 16, 9095},
		{12, 13, 3850},
		{8, 14, 7368},
		{12, 13, 8159},
		{11, 16, 8520}
	},
//
//	 Test # 84
	{
		{16, 15, 6721},
		{15, 12, 8993},
		{9, 8, 7384},
		{13, 10, 4216},
		{15, 11, 8821},
		{13, 8, 8779},
		{14, 9, 6143}
	},
//
//	 Test # 85
	{
		{14, 10, 6871},
		{8, 15, 5538},
		{16, 12, 7608},
		{9, 14, 2177},
		{10, 12, 2679},
		{13, 9, 2420},
		{13, 11, 7965}
	},
//
//	 Test # 86
	{
		{10, 14, 5327},
		{14, 15, 8817},
		{13, 10, 8547},
		{11, 9, 5457},
		{10, 16, 4531},
		{13, 16, 9424},
		{11, 8, 6016}
	},
//
//	 Test # 87
	{
		{9, 8, 2267},
		{8, 12, 3105},
		{15, 9, 9751},
		{14, 8, 7075},
		{10, 9, 1557},
		{11, 13, 4344},
		{10, 12, 7280}
	},
//
//	 Test # 88
	{
		{11, 15, 2970},
		{14, 15, 3255},
		{8, 13, 9457},
		{14, 8, 5474},
		{14, 13, 1710},
		{9, 13, 6320},
		{12, 13, 3137}
	},
//
//	 Test # 89
	{
		{9, 12, 7725},
		{14, 13, 7308},
		{13, 10, 4578},
		{16, 12, 8621},
		{10, 9, 7200},
		{12, 11, 3704},
		{15, 16, 2897}
	},
//
//	 Test # 90
	{
		{11, 9, 1511},
		{10, 16, 2260},
		{14, 11, 4769},
		{13, 8, 7910},
		{9, 8, 1531},
		{16, 10, 8586},
		{13, 11, 8938}
	}
};

Тесты с 13 ключами

static Spanner allTheTests[totalTests][13] = { 
//
//	 Test # 1
	{
		{13, 9, 1786},
		{13, 8, 5945},
		{16, 8, 6021},
		{13, 16, 7513},
		{9, 16, 2296},
		{9, 13, 9310},
		{14, 15, 5789},
		{9, 13, 6351},
		{13, 16, 2669},
		{13, 12, 5407},
		{16, 10, 5281},
		{16, 8, 9390},
		{8, 16, 4113}
	},
//
//	 Test # 2
	{
		{11, 15, 5001},
		{11, 14, 4517},
		{9, 8, 9194},
		{15, 14, 5734},
		{12, 13, 5527},
		{16, 9, 2349},
		{14, 8, 3954},
		{14, 15, 2222},
		{12, 14, 3625},
		{16, 15, 9621},
		{15, 11, 5050},
		{13, 12, 3638},
		{14, 13, 9987}
	},
//
//	 Test # 3
	{
		{12, 8, 6189},
		{10, 15, 1859},
		{12, 11, 2951},
		{13, 10, 1775},
		{13, 16, 7448},
		{8, 16, 6117},
		{12, 9, 5821},
		{15, 11, 9906},
		{10, 14, 8737},
		{14, 15, 9074},
		{14, 10, 5798},
		{8, 11, 7351},
		{11, 13, 6110}
	},
//
//	 Test # 4
	{
		{15, 8, 7302},
		{8, 14, 4550},
		{15, 13, 5680},
		{9, 16, 5906},
		{12, 16, 5661},
		{11, 16, 6239},
		{13, 8, 2009},
		{14, 11, 6348},
		{11, 15, 6402},
		{11, 16, 3501},
		{15, 9, 5522},
		{9, 11, 3370},
		{13, 9, 8394}
	},
//
//	 Test # 5
	{
		{9, 13, 8506},
		{10, 9, 3446},
		{9, 13, 8055},
		{15, 16, 3984},
		{16, 11, 5263},
		{13, 11, 8296},
		{11, 8, 8588},
		{13, 16, 3227},
		{16, 11, 6247},
		{11, 13, 7284},
		{10, 15, 6224},
		{9, 11, 9763},
		{8, 13, 6716}
	},
//
//	 Test # 6
	{
		{14, 8, 3212},
		{14, 16, 6545},
		{10, 16, 8367},
		{13, 12, 8685},
		{12, 8, 6851},
		{13, 9, 9188},
		{11, 13, 3015},
		{14, 16, 4390},
		{16, 8, 4007},
		{16, 15, 4729},
		{16, 13, 2328},
		{16, 12, 1587},
		{10, 8, 6209}
	},
//
//	 Test # 7
	{
		{12, 16, 5910},
		{15, 13, 8633},
		{13, 16, 3658},
		{15, 13, 7687},
		{15, 14, 9602},
		{11, 14, 2390},
		{10, 8, 9139},
		{16, 10, 8001},
		{15, 14, 1722},
		{13, 8, 2246},
		{9, 10, 3493},
		{8, 9, 1728},
		{16, 8, 1592}
	},
//
//	 Test # 8
	{
		{10, 14, 7382},
		{16, 8, 5974},
		{9, 12, 3819},
		{12, 10, 3151},
		{8, 14, 8340},
		{12, 14, 4151},
		{14, 16, 6070},
		{12, 8, 9494},
		{15, 9, 6072},
		{16, 14, 6931},
		{16, 8, 2600},
		{14, 12, 7555},
		{14, 16, 2921}
	},
//
//	 Test # 9
	{
		{8, 10, 8700},
		{15, 9, 8196},
		{12, 16, 6869},
		{11, 8, 3652},
		{9, 12, 7345},
		{11, 10, 3749},
		{10, 9, 7685},
		{8, 10, 2293},
		{15, 9, 8794},
		{15, 12, 4720},
		{14, 9, 6164},
		{16, 9, 2700},
		{16, 8, 9370}
	},
//
//	 Test # 10
	{
		{14, 13, 9727},
		{10, 14, 6727},
		{11, 16, 7788},
		{16, 10, 2689},
		{13, 14, 3846},
		{12, 8, 2986},
		{10, 8, 5047},
		{11, 16, 5743},
		{16, 12, 8591},
		{16, 12, 5048},
		{8, 12, 8115},
		{11, 10, 6479},
		{9, 10, 3371}
	},
//
//	 Test # 11
	{
		{12, 14, 9522},
		{9, 12, 4782},
		{14, 9, 1822},
		{15, 14, 2083},
		{10, 16, 1601},
		{15, 14, 5369},
		{10, 15, 5574},
		{8, 12, 8236},
		{9, 10, 1601},
		{14, 15, 2054},
		{13, 9, 5966},
		{8, 15, 2199},
		{14, 10, 1774}
	},
//
//	 Test # 12
	{
		{11, 12, 8709},
		{12, 10, 9376},
		{12, 15, 5622},
		{12, 9, 6979},
		{9, 14, 7768},
		{15, 8, 8584},
		{12, 16, 3031},
		{12, 16, 3936},
		{14, 15, 6339},
		{8, 13, 4838},
		{14, 13, 2112},
		{16, 14, 6765},
		{16, 14, 8601}
	},
//
//	 Test # 13
	{
		{8, 15, 5244},
		{8, 12, 8373},
		{14, 12, 9749},
		{9, 8, 5293},
		{11, 15, 7490},
		{15, 13, 2787},
		{13, 12, 5059},
		{12, 9, 2506},
		{9, 15, 7857},
		{9, 8, 3433},
		{8, 9, 8822},
		{10, 13, 5709},
		{11, 15, 6904}
	},
//
//	 Test # 14
	{
		{12, 8, 9289},
		{16, 9, 5536},
		{15, 9, 3274},
		{12, 11, 3379},
		{16, 9, 9635},
		{14, 15, 4143},
		{8, 9, 2747},
		{13, 12, 4606},
		{13, 15, 3907},
		{11, 16, 3656},
		{8, 9, 3578},
		{15, 16, 2227},
		{11, 9, 6046}
	},
//
//	 Test # 15
	{
		{12, 13, 6684},
		{16, 13, 6364},
		{10, 9, 9803},
		{13, 8, 8297},
		{11, 14, 9133},
		{8, 11, 3909},
		{12, 8, 7008},
		{12, 9, 6813},
		{11, 14, 9790},
		{10, 12, 4928},
		{13, 8, 8976},
		{15, 12, 5768},
		{14, 11, 4474}
	},
//
//	 Test # 16
	{
		{9, 12, 7239},
		{10, 15, 6596},
		{9, 14, 7037},
		{12, 15, 1669},
		{8, 9, 9457},
		{16, 9, 6517},
		{13, 14, 3348},
		{13, 16, 8264},
		{13, 15, 5381},
		{12, 14, 3656},
		{8, 15, 3243},
		{9, 16, 3168},
		{11, 15, 2236}
	},
//
//	 Test # 17
	{
		{14, 12, 9463},
		{11, 10, 8838},
		{8, 11, 3349},
		{9, 10, 5794},
		{11, 14, 4560},
		{11, 13, 4681},
		{8, 12, 7750},
		{10, 12, 3246},
		{12, 8, 3105},
		{14, 16, 8754},
		{14, 13, 4971},
		{10, 13, 1871},
		{13, 16, 8437}
	},
//
//	 Test # 18
	{
		{8, 15, 3152},
		{9, 15, 4137},
		{10, 9, 7911},
		{11, 13, 8839},
		{15, 12, 7206},
		{11, 16, 7503},
		{9, 15, 5720},
		{14, 15, 5930},
		{15, 10, 2363},
		{9, 16, 1696},
		{9, 15, 3527},
		{12, 16, 6830},
		{13, 9, 9466}
	},
//
//	 Test # 19
	{
		{10, 9, 6151},
		{10, 8, 2695},
		{8, 16, 8333},
		{16, 10, 2916},
		{16, 15, 2348},
		{15, 16, 6835},
		{16, 12, 1791},
		{10, 13, 2689},
		{14, 13, 2710},
		{9, 11, 7293},
		{11, 8, 9404},
		{12, 8, 5256},
		{15, 11, 2987}
	},
//
//	 Test # 20
	{
		{13, 16, 5699},
		{12, 14, 6748},
		{14, 16, 6178},
		{10, 13, 7899},
		{15, 8, 2972},
		{11, 10, 4170},
		{16, 13, 2015},
		{16, 12, 2730},
		{15, 10, 3816},
		{12, 11, 1768},
		{13, 15, 6493},
		{15, 13, 8614},
		{13, 10, 9406}
	},
//
//	 Test # 21
	{
		{9, 11, 5634},
		{15, 16, 9009},
		{15, 11, 6572},
		{14, 11, 6608},
		{16, 8, 2941},
		{11, 10, 7810},
		{15, 12, 8378},
		{15, 9, 4976},
		{9, 15, 2728},
		{12, 10, 6518},
		{16, 13, 7605},
		{11, 14, 6074},
		{15, 9, 4811}
	},
//
//	 Test # 22
	{
		{11, 13, 4692},
		{9, 8, 4684},
		{9, 16, 4453},
		{14, 11, 2242},
		{14, 11, 7219},
		{10, 8, 7595},
		{15, 11, 4269},
		{15, 8, 5161},
		{10, 14, 4544},
		{16, 10, 5565},
		{10, 11, 2061},
		{13, 11, 2037},
		{9, 8, 9904}
	},
//
//	 Test # 23
	{
		{13, 11, 2330},
		{8, 10, 7470},
		{12, 15, 3974},
		{12, 11, 8200},
		{16, 15, 9738},
		{14, 12, 7477},
		{11, 9, 7364},
		{12, 14, 2620},
		{14, 15, 9349},
		{8, 12, 8601},
		{8, 9, 2312},
		{8, 16, 2835},
		{14, 12, 9606}
	},
//
//	 Test # 24
	{
		{9, 10, 6639},
		{14, 8, 6576},
		{16, 15, 6702},
		{12, 9, 6076},
		{14, 11, 7138},
		{15, 14, 4119},
		{11, 15, 6057},
		{16, 9, 4982},
		{11, 9, 8167},
		{14, 13, 3036},
		{14, 16, 5223},
		{12, 10, 2679},
		{10, 16, 2300}
	},
//
//	 Test # 25
	{
		{9, 13, 2616},
		{12, 13, 8377},
		{10, 13, 7360},
		{12, 14, 6726},
		{10, 11, 4435},
		{12, 8, 7350},
		{12, 14, 5001},
		{9, 15, 6483},
		{15, 13, 3221},
		{11, 14, 4223},
		{15, 13, 3273},
		{8, 12, 4748},
		{11, 14, 9817}
	},
//
//	 Test # 26
	{
		{15, 16, 9897},
		{8, 10, 7546},
		{12, 9, 2290},
		{16, 9, 5611},
		{8, 10, 8776},
		{10, 11, 5319},
		{12, 16, 2882},
		{11, 10, 9416},
		{15, 14, 8047},
		{11, 10, 4747},
		{14, 11, 3586},
		{15, 13, 9479},
		{14, 16, 3892}
	},
//
//	 Test # 27
	{
		{9, 13, 5493},
		{12, 15, 8426},
		{11, 10, 5250},
		{11, 13, 6228},
		{15, 11, 6453},
		{9, 10, 2901},
		{10, 14, 8759},
		{10, 12, 2140},
		{16, 13, 8959},
		{15, 11, 8665},
		{8, 16, 8380},
		{8, 11, 4862},
		{11, 16, 6741}
	},
//
//	 Test # 28
	{
		{10, 11, 2328},
		{13, 14, 2942},
		{9, 12, 3796},
		{11, 14, 7664},
		{10, 14, 3423},
		{14, 10, 6694},
		{9, 14, 8212},
		{11, 14, 5139},
		{8, 13, 9227},
		{10, 13, 2698},
		{14, 11, 3502},
		{8, 11, 3539},
		{11, 16, 8900}
	},
//
//	 Test # 29
	{
		{9, 16, 2113},
		{15, 14, 5543},
		{14, 10, 3152},
		{11, 10, 5335},
		{12, 8, 1920},
		{16, 12, 3593},
		{13, 12, 3246},
		{14, 13, 1559},
		{9, 16, 3956},
		{9, 13, 4033},
		{15, 12, 6880},
		{15, 16, 5973},
		{16, 10, 2037}
	},
//
//	 Test # 30
	{
		{14, 10, 6186},
		{8, 13, 1824},
		{13, 16, 1541},
		{10, 11, 6006},
		{15, 9, 9271},
		{10, 8, 5649},
		{11, 12, 5350},
		{9, 8, 5697},
		{14, 12, 2312},
		{10, 16, 4899},
		{9, 14, 3245},
		{12, 14, 9660},
		{8, 10, 4663}
	},
//
//	 Test # 31
	{
		{12, 9, 9133},
		{14, 9, 7136},
		{12, 13, 1794},
		{13, 12, 7370},
		{10, 16, 4472},
		{13, 15, 3547},
		{15, 8, 5149},
		{15, 9, 8851},
		{9, 13, 2405},
		{9, 12, 9134},
		{11, 12, 7756},
		{15, 11, 6702},
		{12, 11, 2997}
	},
//
//	 Test # 32
	{
		{15, 12, 7002},
		{10, 11, 9009},
		{9, 8, 5176},
		{14, 8, 2507},
		{8, 14, 8964},
		{11, 9, 2498},
		{9, 15, 6218},
		{8, 13, 7256},
		{16, 9, 6847},
		{14, 10, 7105},
		{15, 11, 6830},
		{13, 9, 1942},
		{15, 14, 3839}
	},
//
//	 Test # 33
	{
		{12, 8, 7752},
		{13, 16, 7720},
		{12, 8, 6085},
		{9, 14, 2548},
		{15, 16, 8285},
		{10, 14, 6492},
		{16, 14, 2955},
		{16, 8, 7322},
		{9, 11, 1679},
		{10, 14, 3097},
		{10, 14, 1541},
		{14, 15, 5557},
		{8, 16, 2559}
	},
//
//	 Test # 34
	{
		{9, 15, 4677},
		{12, 11, 2000},
		{13, 12, 1786},
		{12, 15, 8794},
		{12, 14, 5396},
		{15, 10, 4915},
		{15, 9, 5995},
		{15, 12, 8569},
		{12, 9, 1621},
		{15, 9, 7104},
		{15, 8, 1816},
		{13, 16, 5002},
		{14, 11, 9225}
	},
//
//	 Test # 35
	{
		{9, 16, 6118},
		{14, 15, 4047},
		{12, 14, 5979},
		{10, 9, 3348},
		{11, 14, 1716},
		{11, 15, 4887},
		{13, 16, 3568},
		{9, 12, 8653},
		{16, 9, 7683},
		{11, 14, 2881},
		{12, 11, 2572},
		{13, 15, 5456},
		{15, 9, 7861}
	},
//
//	 Test # 36
	{
		{16, 12, 8407},
		{15, 12, 7867},
		{16, 8, 3869},
		{15, 14, 2710},
		{16, 13, 3890},
		{12, 15, 5607},
		{11, 14, 7192},
		{16, 11, 7161},
		{9, 8, 9730},
		{12, 10, 3099},
		{15, 14, 7165},
		{12, 8, 2927},
		{8, 9, 6461}
	},
//
//	 Test # 37
	{
		{15, 11, 2607},
		{15, 13, 7763},
		{14, 8, 7608},
		{10, 8, 4092},
		{13, 11, 6865},
		{13, 15, 4415},
		{14, 12, 1691},
		{16, 8, 4644},
		{14, 10, 3594},
		{10, 14, 1671},
		{11, 14, 3358},
		{14, 8, 4192},
		{9, 11, 3703}
	},
//
//	 Test # 38
	{
		{9, 11, 2832},
		{12, 14, 6130},
		{12, 16, 7520},
		{16, 8, 1898},
		{11, 13, 6095},
		{12, 11, 2800},
		{13, 11, 3683},
		{15, 12, 8115},
		{16, 8, 8011},
		{8, 14, 7327},
		{10, 16, 5532},
		{16, 12, 9566},
		{12, 10, 9081}
	},
//
//	 Test # 39
	{
		{14, 8, 7487},
		{9, 13, 7511},
		{13, 12, 5496},
		{14, 15, 8159},
		{13, 15, 3281},
		{8, 9, 2223},
		{11, 14, 6561},
		{8, 14, 8943},
		{8, 15, 4493},
		{13, 16, 3487},
		{15, 14, 7447},
		{15, 9, 8334},
		{10, 9, 5814}
	},
//
//	 Test # 40
	{
		{9, 15, 9080},
		{10, 13, 9569},
		{10, 8, 2042},
		{14, 8, 6487},
		{11, 10, 3246},
		{13, 15, 6623},
		{13, 15, 3322},
		{15, 14, 5604},
		{10, 13, 2494},
		{11, 16, 3250},
		{11, 9, 8775},
		{13, 12, 9448},
		{9, 11, 7844}
	},
//
//	 Test # 41
	{
		{11, 13, 2740},
		{8, 12, 1898},
		{11, 15, 5592},
		{8, 9, 5950},
		{13, 8, 5961},
		{13, 12, 8958},
		{11, 9, 6783},
		{15, 9, 5025},
		{15, 9, 7449},
		{9, 11, 8364},
		{16, 15, 7307},
		{16, 10, 5263},
		{8, 13, 8881}
	},
//
//	 Test # 42
	{
		{12, 10, 7492},
		{16, 11, 9872},
		{12, 11, 9388},
		{15, 16, 5563},
		{12, 10, 6736},
		{16, 9, 5194},
		{8, 15, 6878},
		{10, 16, 6129},
		{8, 12, 8624},
		{9, 8, 5724},
		{13, 8, 6317},
		{16, 11, 9585},
		{15, 8, 6396}
	},
//
//	 Test # 43
	{
		{14, 11, 2501},
		{16, 14, 9439},
		{11, 8, 3094},
		{13, 11, 2549},
		{10, 8, 3056},
		{10, 12, 4859},
		{9, 16, 7053},
		{12, 10, 7355},
		{14, 9, 4920},
		{14, 10, 6377},
		{10, 8, 7417},
		{16, 11, 6756},
		{13, 12, 8401}
	},
//
//	 Test # 44
	{
		{14, 9, 7437},
		{14, 11, 4572},
		{8, 12, 6009},
		{8, 11, 8696},
		{11, 12, 4579},
		{8, 13, 8797},
		{10, 9, 3736},
		{10, 8, 9252},
		{16, 9, 2312},
		{14, 13, 5407},
		{8, 9, 3525},
		{8, 14, 1690},
		{14, 11, 2952}
	},
//
//	 Test # 45
	{
		{11, 15, 7457},
		{14, 11, 5687},
		{11, 15, 5980},
		{13, 8, 5387},
		{8, 10, 2537},
		{10, 16, 9750},
		{11, 14, 6908},
		{11, 9, 7564},
		{8, 11, 4670},
		{14, 11, 8253},
		{11, 15, 3042},
		{9, 12, 6201},
		{15, 10, 9748}
	},
//
//	 Test # 46
	{
		{13, 14, 2034},
		{8, 9, 4114},
		{8, 10, 5763},
		{8, 11, 1965},
		{16, 11, 7543},
		{13, 15, 8186},
		{11, 8, 6808},
		{8, 11, 8219},
		{11, 10, 4420},
		{12, 8, 6460},
		{13, 14, 7675},
		{13, 12, 7338},
		{14, 11, 4583}
	},
//
//	 Test # 47
	{
		{15, 13, 6927},
		{13, 14, 9511},
		{13, 9, 6512},
		{10, 11, 9997},
		{10, 15, 6969},
		{8, 15, 5574},
		{12, 11, 5604},
		{8, 11, 2422},
		{10, 13, 8607},
		{10, 16, 5706},
		{11, 10, 5120},
		{14, 13, 3363},
		{13, 11, 3537}
	},
//
//	 Test # 48
	{
		{16, 14, 4644},
		{12, 14, 4525},
		{15, 14, 7457},
		{14, 15, 5832},
		{10, 14, 7970},
		{14, 10, 5201},
		{16, 11, 4340},
		{14, 12, 8101},
		{9, 8, 1644},
		{13, 15, 3589},
		{8, 9, 6595},
		{16, 12, 7712},
		{9, 8, 5309}
	},
//
//	 Test # 49
	{
		{8, 14, 3894},
		{16, 8, 3654},
		{13, 10, 7912},
		{8, 15, 5091},
		{8, 14, 4494},
		{9, 12, 8660},
		{16, 8, 9602},
		{10, 9, 9519},
		{13, 10, 7740},
		{10, 15, 8012},
		{11, 12, 9509},
		{15, 12, 7686},
		{15, 12, 9470}
	},
//
//	 Test # 50
	{
		{15, 14, 9378},
		{8, 10, 2693},
		{8, 12, 4990},
		{15, 13, 4055},
		{13, 8, 4582},
		{8, 15, 3037},
		{16, 15, 3504},
		{15, 11, 4437},
		{12, 14, 9942},
		{9, 15, 6393},
		{14, 12, 4252},
		{13, 15, 2608},
		{13, 12, 5538}
	}
};

Тесты с 19 ключами

static Spanner allTheTests[totalTests][19] = { 
//
//	 Test # 1
	{
		{12, 11, 6084},
		{16, 14, 3673},
		{10, 12, 5911},
		{13, 16, 4017},
		{14, 15, 9670},
		{9, 16, 6571},
		{8, 13, 6841},
		{16, 8, 9122},
		{12, 8, 9284},
		{11, 13, 7961},
		{12, 16, 9548},
		{14, 10, 6349},
		{16, 9, 6022},
		{14, 9, 4504},
		{11, 10, 4142},
		{12, 15, 6424},
		{8, 13, 5463},
		{8, 11, 6093},
		{11, 15, 5180}
	},
//
//	 Test # 2
	{
		{10, 15, 1651},
		{16, 10, 5299},
		{8, 10, 8238},
		{8, 14, 5277},
		{11, 12, 9848},
		{12, 13, 1828},
		{10, 14, 4461},
		{14, 9, 4823},
		{8, 15, 6959},
		{16, 12, 1829},
		{12, 14, 9553},
		{14, 16, 7592},
		{11, 15, 4020},
		{9, 14, 1699},
		{14, 9, 8876},
		{8, 14, 2430},
		{11, 15, 7336},
		{11, 15, 4795},
		{8, 9, 6471}
	},
//
//	 Test # 3
	{
		{14, 10, 5493},
		{8, 13, 4985},
		{15, 9, 2253},
		{16, 13, 6306},
		{13, 16, 3181},
		{9, 8, 3955},
		{14, 8, 5873},
		{10, 14, 2035},
		{8, 10, 5834},
		{16, 9, 8638},
		{16, 8, 8713},
		{16, 11, 8756},
		{10, 11, 5408},
		{9, 10, 8068},
		{8, 10, 6570},
		{9, 16, 5141},
		{13, 16, 2762},
		{9, 13, 8453},
		{14, 13, 7274}
	},
//
//	 Test # 4
	{
		{14, 16, 3691},
		{13, 9, 2445},
		{15, 11, 9326},
		{15, 14, 8201},
		{13, 10, 2243},
		{16, 13, 3191},
		{15, 8, 1682},
		{12, 10, 5918},
		{12, 15, 5106},
		{15, 11, 7722},
		{8, 10, 7456},
		{9, 11, 6594},
		{15, 9, 8762},
		{12, 9, 9142},
		{13, 16, 4105},
		{16, 12, 5229},
		{13, 16, 3714},
		{16, 15, 2081},
		{8, 16, 7694}
	},
//
//	 Test # 5
	{
		{15, 8, 5754},
		{10, 14, 4887},
		{15, 13, 6751},
		{16, 8, 6969},
		{13, 16, 1611},
		{11, 13, 7336},
		{12, 11, 4470},
		{10, 8, 6766},
		{13, 9, 8695},
		{10, 9, 3399},
		{12, 11, 5377},
		{9, 14, 7479},
		{13, 9, 2298},
		{13, 14, 5859},
		{9, 11, 1951},
		{10, 14, 5533},
		{12, 15, 5318},
		{9, 13, 8212},
		{10, 13, 3904}
	},
//
//	 Test # 6
	{
		{14, 15, 2242},
		{11, 15, 5143},
		{15, 11, 3107},
		{15, 8, 7606},
		{8, 10, 7608},
		{9, 8, 3012},
		{9, 10, 4857},
		{8, 11, 7335},
		{13, 14, 6092},
		{14, 15, 6029},
		{15, 11, 7296},
		{11, 15, 4924},
		{13, 12, 9693},
		{10, 14, 2557},
		{14, 10, 3054},
		{13, 11, 4397},
		{10, 11, 4014},
		{12, 9, 7340},
		{8, 16, 5777}
	},
//
//	 Test # 7
	{
		{16, 9, 2045},
		{16, 8, 1721},
		{8, 12, 1555},
		{11, 15, 4253},
		{9, 8, 8067},
		{9, 11, 6347},
		{8, 12, 2285},
		{10, 14, 8138},
		{12, 15, 6453},
		{14, 16, 8103},
		{12, 9, 6059},
		{10, 14, 9220},
		{8, 14, 5330},
		{16, 13, 3386},
		{9, 10, 5618},
		{13, 8, 5946},
		{10, 11, 8969},
		{9, 15, 1814},
		{13, 11, 5592}
	},
//
//	 Test # 8
	{
		{13, 16, 8531},
		{9, 15, 3647},
		{10, 13, 6816},
		{15, 14, 2222},
		{16, 15, 3620},
		{12, 16, 9254},
		{10, 14, 3677},
		{14, 16, 2539},
		{14, 15, 3849},
		{9, 14, 1520},
		{14, 10, 6053},
		{12, 14, 4052},
		{10, 9, 5328},
		{9, 10, 9453},
		{13, 16, 4153},
		{16, 14, 6879},
		{10, 9, 5781},
		{15, 10, 8719},
		{11, 10, 7945}
	},
//
//	 Test # 9
	{
		{11, 15, 9459},
		{10, 16, 6731},
		{8, 15, 3745},
		{16, 13, 6163},
		{14, 9, 1516},
		{10, 11, 8911},
		{15, 10, 5036},
		{15, 11, 8467},
		{15, 11, 9109},
		{14, 15, 3432},
		{10, 14, 8182},
		{15, 12, 6779},
		{9, 14, 8898},
		{16, 13, 8253},
		{15, 11, 6594},
		{14, 9, 3488},
		{14, 15, 6511},
		{10, 15, 1779},
		{9, 12, 2681}
	},
//
//	 Test # 10
	{
		{9, 13, 9692},
		{14, 10, 5034},
		{9, 11, 7847},
		{11, 14, 1597},
		{9, 11, 8727},
		{8, 11, 3564},
		{10, 11, 2207},
		{12, 10, 7007},
		{10, 14, 4675},
		{15, 12, 2543},
		{16, 9, 4008},
		{11, 13, 2402},
		{14, 13, 5447},
		{15, 9, 6998},
		{16, 11, 2207},
		{16, 14, 2561},
		{12, 16, 3355},
		{16, 11, 4867},
		{13, 12, 6961}
	},
//
//	 Test # 11
	{
		{9, 10, 6475},
		{9, 14, 8560},
		{11, 15, 5070},
		{11, 13, 5659},
		{10, 16, 3798},
		{9, 15, 3555},
		{10, 11, 3818},
		{12, 15, 5864},
		{16, 12, 2962},
		{14, 12, 5006},
		{16, 10, 4939},
		{11, 15, 3782},
		{13, 16, 7711},
		{16, 14, 9255},
		{16, 12, 3121},
		{9, 13, 8278},
		{13, 8, 5559},
		{12, 10, 9051},
		{10, 8, 9562}
	},
//
//	 Test # 12
	{
		{15, 10, 5550},
		{14, 8, 7073},
		{12, 11, 6750},
		{8, 9, 2589},
		{11, 15, 8976},
		{16, 14, 8737},
		{11, 8, 3149},
		{12, 11, 3216},
		{12, 13, 6443},
		{14, 11, 6221},
		{8, 10, 4561},
		{9, 10, 5183},
		{13, 12, 3173},
		{16, 12, 8015},
		{14, 15, 6196},
		{13, 8, 3588},
		{13, 10, 5004},
		{14, 12, 2467},
		{16, 8, 2922}
	},
//
//	 Test # 13
	{
		{10, 16, 1581},
		{12, 13, 6407},
		{16, 13, 8608},
		{9, 14, 5390},
		{15, 8, 8714},
		{12, 16, 8088},
		{11, 15, 3838},
		{15, 8, 2892},
		{16, 8, 2351},
		{8, 16, 8567},
		{8, 13, 8606},
		{11, 12, 2694},
		{10, 16, 9633},
		{11, 14, 5741},
		{11, 15, 4321},
		{11, 12, 3206},
		{12, 13, 9941},
		{13, 14, 4515},
		{11, 13, 3974}
	},
//
//	 Test # 14
	{
		{9, 8, 4814},
		{12, 11, 2673},
		{11, 9, 1568},
		{15, 14, 1632},
		{9, 10, 9098},
		{13, 14, 2130},
		{16, 13, 6405},
		{12, 14, 2530},
		{14, 8, 3138},
		{12, 8, 3002},
		{12, 15, 8230},
		{9, 16, 3146},
		{13, 10, 2057},
		{13, 9, 2925},
		{15, 10, 8774},
		{12, 10, 9731},
		{10, 8, 9707},
		{13, 14, 6329},
		{10, 8, 6656}
	},
//
//	 Test # 15
	{
		{8, 11, 6360},
		{15, 12, 6318},
		{12, 9, 2157},
		{16, 15, 8115},
		{12, 9, 6890},
		{12, 10, 2802},
		{13, 12, 7962},
		{16, 14, 5263},
		{8, 11, 8065},
		{9, 10, 7230},
		{12, 13, 8259},
		{16, 12, 2059},
		{8, 9, 9539},
		{8, 15, 7533},
		{10, 16, 3441},
		{14, 9, 5279},
		{14, 13, 3815},
		{9, 14, 8597},
		{11, 10, 8270}
	},
//
//	 Test # 16
	{
		{14, 13, 2785},
		{14, 8, 8465},
		{11, 16, 1853},
		{14, 13, 3266},
		{12, 14, 5610},
		{15, 16, 5037},
		{11, 10, 4444},
		{13, 8, 3062},
		{12, 16, 3540},
		{15, 12, 2162},
		{10, 9, 7661},
		{15, 10, 2476},
		{9, 8, 6674},
		{13, 14, 2853},
		{10, 9, 5601},
		{10, 13, 5676},
		{10, 16, 3655},
		{15, 11, 2706},
		{9, 8, 6453}
	},
//
//	 Test # 17
	{
		{8, 14, 4818},
		{15, 11, 3096},
		{9, 8, 4054},
		{8, 10, 4304},
		{8, 15, 6646},
		{10, 14, 6574},
		{16, 13, 9232},
		{11, 15, 2994},
		{12, 16, 3963},
		{16, 8, 8242},
		{8, 9, 8270},
		{14, 11, 3319},
		{13, 15, 6803},
		{16, 15, 2028},
		{15, 11, 6163},
		{16, 8, 2990},
		{15, 14, 2037},
		{11, 15, 6039},
		{11, 12, 9410}
	},
//
//	 Test # 18
	{
		{16, 15, 8611},
		{13, 10, 4832},
		{14, 10, 9911},
		{15, 12, 2374},
		{10, 15, 4748},
		{11, 16, 8346},
		{14, 8, 8105},
		{11, 9, 7097},
		{16, 13, 4719},
		{15, 9, 1508},
		{16, 15, 6785},
		{15, 12, 8327},
		{12, 9, 6547},
		{16, 13, 7913},
		{9, 14, 5856},
		{8, 11, 6834},
		{15, 8, 4310},
		{9, 12, 3626},
		{15, 8, 9620}
	},
//
//	 Test # 19
	{
		{8, 12, 5073},
		{9, 10, 4648},
		{9, 11, 8566},
		{10, 13, 3380},
		{11, 9, 3205},
		{16, 8, 1582},
		{12, 16, 7573},
		{13, 12, 2473},
		{13, 16, 1657},
		{12, 11, 7477},
		{8, 16, 3439},
		{14, 13, 7716},
		{11, 9, 3899},
		{11, 13, 5005},
		{9, 12, 5003},
		{8, 13, 5629},
		{16, 12, 9530},
		{14, 9, 8617},
		{16, 11, 2525}
	},
//
//	 Test # 20
	{
		{13, 16, 5863},
		{15, 16, 9434},
		{8, 11, 3450},
		{12, 16, 2577},
		{9, 14, 3608},
		{10, 16, 2444},
		{14, 10, 9338},
		{10, 15, 2623},
		{13, 9, 7340},
		{13, 8, 9442},
		{10, 13, 3697},
		{10, 13, 6915},
		{16, 9, 8529},
		{10, 8, 2971},
		{11, 16, 9429},
		{15, 8, 2060},
		{13, 15, 9547},
		{12, 9, 9461},
		{8, 12, 2713}
	},
//
//	 Test # 21
	{
		{16, 15, 5833},
		{16, 15, 5619},
		{10, 8, 8701},
		{10, 8, 1511},
		{8, 12, 4564},
		{8, 15, 6611},
		{10, 8, 6332},
		{8, 13, 9419},
		{16, 9, 1528},
		{14, 9, 1736},
		{8, 9, 8690},
		{16, 14, 4674},
		{12, 10, 4815},
		{10, 16, 5433},
		{16, 11, 1932},
		{11, 9, 5057},
		{10, 16, 4084},
		{8, 12, 7814},
		{14, 15, 8905}
	},
//
//	 Test # 22
	{
		{15, 12, 7778},
		{14, 16, 3221},
		{15, 12, 2552},
		{15, 13, 5181},
		{15, 16, 9064},
		{8, 15, 7233},
		{10, 15, 7539},
		{16, 15, 2711},
		{12, 15, 1583},
		{16, 12, 4485},
		{8, 16, 4269},
		{15, 10, 4670},
		{8, 9, 4863},
		{14, 16, 2023},
		{15, 16, 7495},
		{10, 12, 2650},
		{10, 14, 7871},
		{16, 14, 7964},
		{10, 11, 7147}
	},
//
//	 Test # 23
	{
		{10, 16, 7053},
		{14, 12, 8542},
		{10, 16, 7939},
		{15, 10, 4331},
		{10, 12, 9399},
		{15, 9, 5238},
		{12, 10, 2800},
		{9, 14, 4590},
		{10, 15, 3807},
		{12, 10, 3418},
		{10, 16, 5373},
		{16, 11, 7970},
		{13, 15, 3226},
		{15, 13, 1687},
		{11, 9, 9427},
		{13, 14, 6760},
		{10, 11, 6250},
		{15, 10, 3481},
		{14, 15, 1600}
	},
//
//	 Test # 24
	{
		{15, 14, 2701},
		{11, 12, 4639},
		{11, 15, 2153},
		{10, 9, 1837},
		{16, 14, 4525},
		{12, 13, 6958},
		{11, 8, 1918},
		{14, 16, 7183},
		{8, 11, 7069},
		{9, 16, 5360},
		{14, 15, 1990},
		{14, 16, 9434},
		{13, 14, 3815},
		{13, 11, 7416},
		{10, 13, 1697},
		{14, 10, 8078},
		{16, 14, 2782},
		{12, 8, 7645},
		{9, 15, 3339}
	},
//
//	 Test # 25
	{
		{12, 16, 5029},
		{12, 11, 3542},
		{11, 13, 9532},
		{13, 16, 2554},
		{9, 11, 8160},
		{8, 16, 5489},
		{9, 13, 2264},
		{13, 9, 9884},
		{12, 15, 9379},
		{16, 14, 6809},
		{8, 16, 3668},
		{8, 9, 6123},
		{10, 8, 4644},
		{16, 8, 6197},
		{15, 11, 3889},
		{11, 10, 3528},
		{14, 8, 7447},
		{12, 14, 1680},
		{8, 16, 7406}
	},
//
//	 Test # 26
	{
		{12, 9, 5084},
		{15, 16, 1742},
		{8, 14, 6146},
		{9, 12, 2616},
		{15, 14, 2390},
		{13, 15, 6307},
		{13, 8, 1991},
		{16, 12, 4061},
		{15, 11, 4622},
		{10, 11, 7894},
		{12, 10, 3647},
		{16, 10, 7109},
		{11, 13, 5348},
		{15, 8, 2692},
		{9, 10, 5627},
		{13, 12, 6827},
		{8, 14, 5143},
		{12, 10, 7423},
		{15, 11, 9102}
	},
//
//	 Test # 27
	{
		{9, 8, 1752},
		{12, 15, 4131},
		{10, 13, 5165},
		{10, 16, 9377},
		{9, 14, 8618},
		{11, 16, 1962},
		{9, 14, 7780},
		{12, 9, 7259},
		{16, 14, 3339},
		{8, 15, 4212},
		{13, 12, 6117},
		{13, 9, 9514},
		{16, 11, 4577},
		{8, 12, 6498},
		{10, 9, 2358},
		{16, 8, 8173},
		{8, 10, 8703},
		{16, 13, 1509},
		{15, 9, 5140}
	},
//
//	 Test # 28
	{
		{10, 16, 9597},
		{14, 15, 4567},
		{15, 9, 7627},
		{16, 11, 5264},
		{16, 8, 5478},
		{11, 9, 3893},
		{16, 15, 6944},
		{12, 14, 6886},
		{9, 8, 5905},
		{8, 13, 4992},
		{11, 8, 9693},
		{14, 11, 2943},
		{12, 13, 2031},
		{11, 14, 1670},
		{9, 14, 2897},
		{12, 15, 8675},
		{9, 15, 7362},
		{11, 8, 4116},
		{10, 12, 6293}
	},
//
//	 Test # 29
	{
		{16, 9, 7616},
		{9, 13, 9933},
		{16, 9, 4928},
		{16, 14, 7176},
		{15, 16, 7812},
		{12, 10, 8971},
		{10, 16, 4367},
		{10, 16, 2861},
		{11, 9, 9956},
		{13, 11, 7744},
		{9, 8, 3412},
		{11, 15, 6191},
		{10, 14, 3803},
		{9, 12, 7626},
		{11, 13, 6647},
		{11, 12, 3192},
		{16, 8, 2547},
		{12, 13, 8238},
		{14, 12, 5414}
	},
//
//	 Test # 30
	{
		{11, 13, 4688},
		{10, 14, 7574},
		{11, 16, 3309},
		{12, 13, 2714},
		{14, 10, 6584},
		{11, 15, 3830},
		{13, 11, 2034},
		{10, 8, 3739},
		{8, 11, 8904},
		{13, 11, 1878},
		{12, 10, 9112},
		{10, 12, 8329},
		{10, 8, 3168},
		{13, 9, 2319},
		{15, 8, 6526},
		{8, 10, 2950},
		{11, 8, 8501},
		{14, 15, 5635},
		{9, 13, 9373}
	},
//
//	 Test # 31
	{
		{9, 15, 3015},
		{14, 16, 7697},
		{13, 14, 6744},
		{14, 9, 9314},
		{11, 13, 4890},
		{11, 9, 4448},
		{12, 14, 4950},
		{10, 15, 2850},
		{8, 13, 6021},
		{16, 13, 3444},
		{14, 8, 6007},
		{15, 11, 9426},
		{9, 10, 5979},
		{9, 15, 4012},
		{12, 10, 3244},
		{15, 12, 8822},
		{16, 14, 3756},
		{8, 12, 5932},
		{16, 13, 2935}
	},
//
//	 Test # 32
	{
		{12, 16, 2131},
		{14, 13, 1688},
		{12, 8, 8837},
		{13, 10, 4107},
		{12, 8, 2738},
		{8, 12, 4491},
		{8, 11, 1759},
		{15, 9, 5693},
		{13, 9, 9837},
		{13, 8, 2981},
		{9, 8, 7542},
		{8, 13, 5479},
		{11, 14, 2987},
		{13, 10, 4965},
		{12, 16, 2859},
		{13, 16, 3206},
		{14, 16, 4072},
		{8, 10, 4682},
		{8, 9, 6154}
	}
};

Результат прогона всех четырёх программ представлен в таблице ниже. В первых двух столбцах количество ключей и номер теста - эта пара уникальна, так что Вы легко можете найти нужный тест в выложенных выше листингах. Цена в копейках, а время в микросекундах. На тех тестах, на которых та или иная программа выдала неверный результат, вручную проставлено время 10 000 000 мкс., что гарантирует, что они окажутся "хуже" любого правильного результата. Всего таких неудачных тестов 28. Пять у программы от AndreyD и 23 у программы от b707.

Ну, давайте сравним скорость работы.

Поскольку тест на тест не приходится, время сравнивалось по отдельным тестам, а потом уже обобщалось на "в среднем".

В таблице ниже слева просуммировано сколько раз (из 172 тестов) какая из программ оказывалась на первом, втором, третьем и четвёртом местах по времени исполнения. Справа же приведены интегральные показатели скорости программ участников, полученные таким образом: количество первых место умноженное на 3 (т.к. обошёл трёх соперников) + количество вторых мест, умноженное на 2 (из тех же соображений) + количество третьих мест (четвёртые не учитывались вовсе).

отсюда сразу же видно, что формально, в среднем моя программа быстрее, но если исправить ошибку в программе b707, то она окажется самой быстродействующей. Ведь 23 в графе "четвёртые места" - это как раз те самые 23 теста с которыми она просто не справилась. На тех тестах, с которыми она справлялась, она была в среднем быстрее всех. Обязательно посмотрите на эвристики, которые там используются, они очень красивые. Очень, надеюсь, что автор выложит ещё и пояснения к ней. Кстати, остальных участников тоже очень прошу выложить пояснения.

ну, а с точки зрения подведения итогов и вручения приза, надо отметить, что программы двух участников - b707 и AndreyD обходили мою на каких-то тестах, а потому им обоим полагается обещанный "спец. приз.".

Таким образом,

1. победителем признаётся Kolyn - единственный из участников, чья программа справилась со всеми тестами.

2. b707 и AndreyD получают специальные призы за то, что их программы оказались быстрее моей на нескольких тестах тестах.

Прошу всех троих прислать мне на elilitko@mail.ru координаты для отправки призов.

P.S.
собственную программу выкладываю, но хочу ещё снабдить её  пояснениями, чтобы превратить в учебный материал, но на это уже нет сил - завтра пояснения выложу. Если кто-то захочет её скорость измерять на своих тестах, не забудьте все печати закомментировать. Программа состоит из 4-х файлов. Для печати отладочной информации нужна библиотека Printing.

Файл .ino

#include <Printing.h>

typedef uint8_t TSize;
typedef uint16_t TPrice;

#include "Spanner.h"

static Spanner spanners[] = {
	{1, 8 , 4},
	{4, 6 , 10},
	{6, 12, 123},
	{2, 6 , 12},
	{8, 1 , 2},
	{6, 10 , 3},	
	{20, 9 , 3},
	{20, 17 , 3},	
	{20, 17 , 4},	
	{1, 8 , 3},	
	{2, 8 , 13},
	{8, 6 , 38208}
};
static uint8_t totalSpanners = sizeof(spanners) / sizeof(spanners[0]);


static inline void printSpanners(const __FlashStringHelper * title) {
	Serial.println(title);
	for (uint8_t i = 0; i < totalSpanners; i++) Serial.println(spanners[i]);
	Serial.println(F("-------"));
}

#include "Sizes.h"
#include "Solution.h"

// Рабочее и "текущее лучшее" решения
Solution currentSolution(0), bestSolution;

//
//	Удаляем дубликаты
//
uint8_t removeDuplicates(void) {
	Spanner::sortBySpanners(spanners, totalSpanners);
	uint8_t removedItemsCount = 0;
	for (uint8_t i = 1; i < totalSpanners; i++) {
		for (; i < totalSpanners && spanners[i] == spanners[i-1]; i++, removedItemsCount++) 
			spanners[i].state = Spanner::stateDuplicate;
	}
	return removedItemsCount;
}

//
//	Создаём массив всех размеров Solution::allSizes
//
bool createSizesArray() {
	uint8_t minSize = 255, maxSize = 0;
	for(uint8_t i = 0; i < totalSpanners; i++) {
		const Spanner & spanner = spanners[i];
		if (spanner.state) continue; // дубликаты нам неинтересны
		if (spanner.size1 < minSize) minSize = spanner.size1;
		if (spanner.size2 > maxSize) maxSize = spanner.size2;
	}
	const bool result = Solution::allSizes.init(maxSize - minSize + 1, minSize);
	if (! result) Serial.println(F("*** ошибка: недостаточно памяти для массива размеров"));
	return result;
}

//
//	Помечаем железобетонные ключи, чтобы исключить их их перебора
// заодно считаем количество разных размеров и заносим в Solution
//
bool markFerroconcretesAndFormSolution(uint8_t & totallyRemoved) {
	Sizes<SSize> sizesArray;
	if (! sizesArray.init(& Solution::allSizes)) {
		Serial.println(F("*** ошибка: недостаточно памяти для массива размеров"));
		return false;
	}

	for(uint8_t i = 0; i < totalSpanners; i++) {
		Spanner * pSpanner = spanners + i;
		if (pSpanner->state) continue; // дубликаты нам неинтересны
		SSize & s1 = sizesArray[pSpanner->size1];
		SSize & s2 = sizesArray[pSpanner->size2];
		s1.counter++; s1.pSpanner = pSpanner;
		s2.counter++; s2.pSpanner = pSpanner;
	}

	totallyRemoved = 0;
	for (uint8_t i = 0; i < sizesArray.length; i++) {
		SSize & curSize = sizesArray.item(i);
		if (curSize.counter == 0) continue;
		Solution::allSizes.totalSizes ++;
		if (curSize.pSpanner->state) continue; // дубликаты нам неинтересны
		if (curSize.counter == 1) {
			currentSolution.pushSpanner(curSize.pSpanner);
			curSize.pSpanner->state = Spanner::stateFerroconcrete;
			totallyRemoved ++;
		}
	}
	sizesArray.freeResources();
	return true;
}

//
//	Помечаем ключи, которые не нужны, когда уже есть 
//	"железобетонное" решение
//
uint8_t excludeHopelessSpanners(void) {
	uint8_t totallyRemoved = 0;
	for(uint8_t i = 0; i < totalSpanners; i++) {
		Spanner & spanner = spanners[i];
		if (spanner.state) continue; // дубликаты и железобетонные нам неинтересны
		if (currentSolution.isNotApplicable(spanner)) {
			spanner.state = Spanner::stateHopeless;
			totallyRemoved ++;
		}
	}
	return totallyRemoved;
}

//
//	Перебор с ветвями и границами
//
void lookForSolution(const uint8_t startIndex = 0) {
	for (uint8_t i = startIndex; i < totalSpanners; i++) {
		const Spanner * const pSpanner = spanners + i;
		if (currentSolution.isOverpriced(* pSpanner, bestSolution.total())) return;
		if (currentSolution.isNotApplicable(* pSpanner)) continue;
		currentSolution.pushSpanner(pSpanner);
		if (currentSolution.isComplete()) {
			bestSolution = currentSolution;
			currentSolution.popSpanner();
			return;
		} else lookForSolution(i + 1);
		currentSolution.popSpanner();
	}
}

//
//	Собственно, всё вместе.
//
void setup(void) {
	Serial.begin(115200);
	printSpanners(F("Ключи в самом начале"));
	const uint8_t duplicates = removeDuplicates();
	currentSolution.init(totalSpanners - duplicates);
	bestSolution.init(totalSpanners - duplicates);
	createSizesArray();
	uint8_t ferroconcretes = 0;
	markFerroconcretesAndFormSolution(ferroconcretes);
	printSpanners(F("После поиска железного решения"));
	printVar(Solution::allSizes.totalSizes);
	Serial.println(currentSolution);
	if (currentSolution.isComplete()) {
		bestSolution = currentSolution;
	} else {
		const uint8_t hopeless = excludeHopelessSpanners();
		printVar(hopeless);
		printSpanners(F("После исключения безнадёжных"));
		Spanner::sortByStates(spanners, totalSpanners);
		totalSpanners -= (duplicates + hopeless + ferroconcretes);
		printVar(totalSpanners);
		printSpanners(F("После удаления всего"));
		lookForSolution();
	}
	Serial.println(bestSolution);
}

void loop(void) {}

Файл Sizes.h

#ifndef	SIZES_H
#define	SIZES_H

struct SSize {
	Spanner * pSpanner;
	uint8_t counter;	
};

struct SizeParameters {
	uint8_t length = 0;
	uint8_t offset = 0;
	uint8_t totalSizes = 0;
};

template<class T>
struct Sizes : public SizeParameters {
	T * sArray = 0;

	bool init(SizeParameters * other) { return init(other->length, other->offset); }
	
	bool init(const uint8_t l, const uint8_t o) {
		length = l;
		offset = o;
		sArray = reinterpret_cast<T *>(calloc(length, sizeof(*sArray)));
		return static_cast<bool>(sArray);
	}

	void freeResources(void) { free(sArray); sArray = nullptr; }
	inline T & operator [] (const uint8_t n) const { return item(n - offset); }
	inline T & item(const uint8_t n) const { return sArray[n]; } // неплохо бы на выход проверять
};

#endif	//	SIZES_H

Файл Solution.h

#ifndef	SOLUTION_H
#define	SOLUTION_H

class Solution : public Printable { 
	const Spanner ** m_stack;
	uint8_t m_stackPtr;
	uint8_t m_notZeroes;
	TPrice m_total;

	inline void push(const Spanner * const sp) { m_stack[m_stackPtr++] = sp; } // проверка на переполнение?
	inline void pop(void) { m_stackPtr--; }

	inline void addSpannerSizes(const Spanner & sp) {
		uint8_t * const sa = allSizes.sArray - allSizes.offset;
		uint8_t * const am1 = sa + sp.size1;
		uint8_t * const am2 = sa + sp.size2;
		if (! * am1) m_notZeroes++;
		if (! * am2) m_notZeroes++;
		(*am1)++;
		(*am2)++;
	}
	
	inline void removeSpannerSizes(const Spanner & sp) {
		uint8_t * const sa = allSizes.sArray - allSizes.offset;
		uint8_t * const am1 = sa + sp.size1;
		uint8_t * const am2 = sa + sp.size2;
		(*am1)--;
		(*am2)--;
		if (! *am1) m_notZeroes--;
		if (! *am2) m_notZeroes--;
	}

public:
	static Sizes<uint8_t> allSizes;
	
	Solution(TPrice iniPrice = UINT16_MAX) : m_stack(nullptr), m_stackPtr(0), m_notZeroes(0), m_total(iniPrice) {}
	~Solution(void) { delete [] m_stack; m_stack = nullptr; }

	bool init(const uint8_t nSpanners) { return (m_stack = new const Spanner * [nSpanners]); }

	inline TPrice total(void) const { return m_total; }

	inline void pushSpanner(const Spanner * const sp) {
		addSpannerSizes(*sp);
		push(sp);
		m_total += sp->price;
	}

	inline void popSpanner(void) {
		const Spanner * const sp = m_stack[m_stackPtr - 1];
		removeSpannerSizes(*sp);
		m_total -= sp->price;
		pop();
	}

	//bool isBetter(const Solution best) const { return m_total < best.m_total; }

	inline bool isOverpriced(const Spanner & spanner, const TPrice bestPrice = UINT16_MAX) const {
		// Если с учётом этого ключа цена превысит "текущую лучшую" - нечего его добавлять
		return spanner.price + m_total >= bestPrice;
	}
	inline bool isNotApplicable(const Spanner & spanner) const {
		const uint8_t * sa = allSizes.sArray - allSizes.offset;
		// если оба размера уже есть в решении, нечего этому ключу тут делать
		return sa[spanner.size1] && sa[spanner.size2]; 
	}

	inline bool isComplete(void) const { return allSizes.totalSizes == m_notZeroes; }

	size_t printTo(Print & p) const { 
		size_t res = p.println(F("Решение: "));
		for (uint8_t i = 0; i < m_stackPtr; i++) {
			res += p.println(* m_stack[i]);
		}
		res += p.print(F("Стоимость: "));
		res += p.println(m_total);
		res += p.print(F("Всего размеров: "));
		res += p.println(m_notZeroes);
		res += p.print(F("Полное: "));
		res += p.println(isComplete() ? F("Да") : F("Нет"));
		return res;
	}

	inline void operator = (const Solution & other);
};

Sizes<uint8_t> Solution::allSizes;

inline void Solution::operator = (const Solution & other) {
	m_stackPtr = other.m_stackPtr;
	m_notZeroes = other.m_notZeroes;
	m_total = other.m_total;
	const size_t totalBytes = sizeof(* m_stack) * m_stackPtr;
//	m_stack = static_cast<Spanner **>(realloc(m_stack, totalBytes));
//	if (m_stack) 
	memcpy(m_stack, other.m_stack, totalBytes);
}

#endif	//	SOLUTION_H

Файл Spanner.h

#ifndef	SPANNER_H
#define	SPANNER_H

struct Spanner : public Printable {
	typedef int (* TCompareFunc)(const void *, const void *);
	enum EState : int8_t { stateHopeless = -3, stateDuplicate = -2, stateFerroconcrete = -1, stateUnknown = 0 };

	TPrice price;
	EState state;
	TSize size1; 
	TSize size2;

	// size1 всегда <= size2, это удобно при сортировке ключей
	constexpr Spanner(const uint8_t s1, const uint8_t s2, const TPrice p) : price(p), state(stateUnknown), size1(min(s1,s2)), size2(max(s1,s2)) {}

	size_t printTo(Print & p) const { 
		return p.print(size1) + p.print('x') + p.print(size2) + p.print(F(": ")) + p.print(price/100.0) + p.print(F(" руб. ")) + printEState(p); 
	}

	size_t printEState(Print &p) const {
		if (state == stateHopeless) return p.print(F("бесперспектиный"));
		if (state == stateDuplicate) return p.print(F("дубликат"));
		if (state == stateFerroconcrete) return p.print(F("железобетонный"));
		return 0;
	}

	 friend bool operator == (const Spanner & s1, const Spanner & s2) {
	 	return s1.size1 == s2.size1 && s1.size2 == s2.size2;
	 }

	static int compareSpanners(const Spanner * a, const Spanner * b) {
		if (a->size1 > b->size1) return 1;
		if (a->size1 < b->size1) return -1;
		if (a->size2 > b->size2) return 1;
		if (a->size2 < b->size2) return -1;
		if (a->price > b->price) return 1;
		if (a->price < b->price) return -1;
		return 0;
	}
	
	static int compareStates(const Spanner * a, const Spanner * b)  {
		if (a->state > b->state) return -1;
		if (a->state < b->state) return 1;
		// если состояние отлично от stateUnknown то нам пофиг их порядок внутри одного состояния
		if (a->state) return 0; 
		// а для stateUnknown отсортируем ещё по возрастанию цены
		if (a->price > b->price) return 1;
		if (a->price < b->price) return -1;
		return 0;
	}

	static void sortBySpanners(Spanner * const sArray, const uint8_t nSize) {
		qsort(sArray, nSize, sizeof(*sArray), reinterpret_cast<TCompareFunc>(compareSpanners));
	} 

	static void sortByStates(Spanner * const sArray, const uint8_t nSize) {
		qsort(sArray, nSize, sizeof(*sArray), reinterpret_cast<TCompareFunc>(compareStates));
	}
};

#endif	//	SPANNER_H

------------------------------------

Действительно Гигантская проведена работа по подведению итогов конкурса, аплодирую стоя.

Уточните, пожалуйста, какие пояснения нужны, я выкладывал словесный алгоритм и старался подписывать комментариями все блоки кода.

Евгений, спасибо огромное за проделанную работу, ну и за похвалу тоже :)

Можете уточнить, как технически вы прогоняли такое количество тестов на наших кодах? Не вставляли же в исходник каждый раз?

Я вижу что у вас коды организованы в массив - но если вставить этот массив в код . у атмеги оперативки вовсе не останется.

Вероятно, я пропустил. Поищу завтра.

Сдублирую с небольшими изменениями (ещё немного дополнил):

Моё виденье каким должен быть алгоритм:

    1. Фильтрация массива ключей. (типа сито)
    2. Если фильтрация не справилась, то перебор сочетаниями без повторений.

Возможно, в процессе фильтрации можно разделить набор на поднаборы и уже к ним применять пункт 2.

Или при грамотно продуманной  фильтрации перебор и не понадобиться.

Алгоритм:

    1) Дубли с высокой ценой, при этом нужно учесть, что ключи могут быть перевёрнутыми, исключаются сразу.
    2) Ключи, в которых размер встречается только один раз (уникальные ключи) или оставшиеся ключи после пункта 5 с этим же условием,  по любому добавляются в набор.
    3) Тут проявляется условие, что у каждого ключа есть два размера не равных между собой. Т.е. на примере набора из задания, который я и буду приводить дальше, 6-8, 9-11, 24-27 уникальные ключи с размерами 6, 11, 27, а размеры 8, 9, 24 уже не нужны для дальнейшей проверки.
    4) При этом ключ 8-9 уже не нужен, т.к. его размеры уже включены в результирующий набор.
    5) Далее могут присутствовать ключи, у которых один размер исключен, можно сравнить его стоимость с остальными ключами с таким же размером и если его цена больше то исключить его. При этом, если кол-во ключей с этим размером был равен 2, то более дешёвый ключ (это тот у которого оба размера раньше не были исключены) становиться уникальным. А его второй размер исключается из дальнейшего перебора.
    6) Повторение в цикле пунктов 2-5 пока есть удаление ключей в этом цикле.
    7) Если что-то останется, то перебор сочетаний без повторений.

Дополнительно:

1) Ссылки и указатели не использовал, т.к. не умею

2) От рекурсии отказался, т.к. она требует много памяти, решил что количество ключей важнее.

3) От размещения массива ключей (размеры и цена) в PROGMEM отказался, т.к. подумал, что это повлияет на скорость выполнения кода.

ЗЫ: много раз менял словесный алгоритм, теперь, вроде, полностью описал. А то был День трезвости, надо было отметить праздник. ))

Взял мегу и написал вот такой "испытательный стенд"

Файл "TestBench.h"

#ifndef	TESTBENCH_H
#define	TESTBENCH_H

#include <EEPROM.h>

#define	FIRST_HALF	true

#include "Spanners12Tests.h"

constexpr char * __nick = (char *) "EP";
constexpr uint16_t eepromAddress = 16;

static int __currentTestNom = 0;


void setupTest(void) {
	EEPROM.get(eepromAddress, __currentTestNom);
	if (__currentTestNom < 0 || __currentTestNom >= totalTests) __currentTestNom = 0;
	EEPROM.put(eepromAddress, __currentTestNom + 1);
	memcpy(spanners, & (allTheTests[__currentTestNom][0]), sizeof(allTheTests[__currentTestNom]));
}

void (* __softReset) (void) = nullptr;

void printTestRes(const uint32_t price, const uint32_t timespan) {
	Serial.print(__nick);
	Serial.print('\t');
	Serial.print(sizeof(spanners)/sizeof(spanners[0]));
	Serial.print('\t');
	Serial.print(__currentTestNom + 1);
	Serial.print('\t');
	Serial.print(price);
	Serial.print('\t');
	Serial.println(timespan);
	Serial.flush();
	if (__currentTestNom + 1 < totalTests) __softReset(); 
	else {
		EEPROM.put(eepromAddress, 0); // для следующего запуска
		while(true);
	}
}

#endif	//	TESTBENCH_H

Файл "TesBench.h" вместе с тремя файлами тестов кидал в папку с испытуемой программой.

В испытуемой программе делал три вещи

1. Вместо определения массива spanners вставлял #include "TestBehcn.h"
2. Перед засечением времени вставлял строку "setupTest();"
3. После отсечки времени, убирал печать результата, а вместо неё вставлял вызов "printTestRes(price, duration);"

(ну, с точностью до имён переменных - принцип такой).

Далее, в файле "TesBench.h" в десятой строке вставлял ник, а в восьмой имя файла с тестами и запускал. Она выполнял один тест, после чего сама ресетилась и выполняла следующий и так пока все не выполнит. Когда все тесты отработают, в мониторе аккуратная табличка. 

Моя IDE не стирает монитор при перезаливке, так что ничего не трогая менял имя файла с тестами и запускал ещё раз. Результаты приписывались в хвост.

Когда все тесты для одного участника выполнены, тупо копировал их прямо в Excel (там не зря через табуляции всё выводится).

И так для всех участников.

Ну, а дальше в экселе обрабатывал.

P.S.
Ах, да, я там выше выкладывал только сами тесты. Если кто захочет "стенд" запускать, то полностью файлы тестов выглядят примерно так:

#ifndef	SPANNERS19TESTS_H
#define	SPANNERS19TESTS_H

static constexpr int totalTests = 32;

static Spanner spanners[19] = {{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0},{0,0,0}}; 

static Spanner allTheTests[totalTests][19] = { 
//
//	 Test # 1
	{
		{12, 11, 6084},
		{16, 14, 3673},
		{10, 12, 5911},
		{13, 16, 4017},
		{14, 15, 9670},
		{9, 16, 6571},
		{8, 13, 6841},
		{16, 8, 9122},
		{12, 8, 9284},
		{11, 13, 7961},
		{12, 16, 9548},
		{14, 10, 6349},
		{16, 9, 6022},
		{14, 9, 4504},
		{11, 10, 4142},
		{12, 15, 6424},
		{8, 13, 5463},
		{8, 11, 6093},
		{11, 15, 5180}
	},
//
//	 Test # 2
	{
		{10, 15, 1651},
		{16, 10, 5299},
		{8, 10, 8238},
		{8, 14, 5277},
		{11, 12, 9848},
		{12, 13, 1828},
		{10, 14, 4461},
		{14, 9, 4823},
		{8, 15, 6959},
		{16, 12, 1829},
		{12, 14, 9553},
		{14, 16, 7592},
		{11, 15, 4020},
		{9, 14, 1699},
		{14, 9, 8876},
		{8, 14, 2430},
		{11, 15, 7336},
		{11, 15, 4795},
		{8, 9, 6471}
	},
//
//	 Test # 3
	{
		{14, 10, 5493},
		{8, 13, 4985},
		{15, 9, 2253},
		{16, 13, 6306},
		{13, 16, 3181},
		{9, 8, 3955},
		{14, 8, 5873},
		{10, 14, 2035},
		{8, 10, 5834},
		{16, 9, 8638},
		{16, 8, 8713},
		{16, 11, 8756},
		{10, 11, 5408},
		{9, 10, 8068},
		{8, 10, 6570},
		{9, 16, 5141},
		{13, 16, 2762},
		{9, 13, 8453},
		{14, 13, 7274}
	},
//
//	 Test # 4
	{
		{14, 16, 3691},
		{13, 9, 2445},
		{15, 11, 9326},
		{15, 14, 8201},
		{13, 10, 2243},
		{16, 13, 3191},
		{15, 8, 1682},
		{12, 10, 5918},
		{12, 15, 5106},
		{15, 11, 7722},
		{8, 10, 7456},
		{9, 11, 6594},
		{15, 9, 8762},
		{12, 9, 9142},
		{13, 16, 4105},
		{16, 12, 5229},
		{13, 16, 3714},
		{16, 15, 2081},
		{8, 16, 7694}
	},
//
//	 Test # 5
	{
		{15, 8, 5754},
		{10, 14, 4887},
		{15, 13, 6751},
		{16, 8, 6969},
		{13, 16, 1611},
		{11, 13, 7336},
		{12, 11, 4470},
		{10, 8, 6766},
		{13, 9, 8695},
		{10, 9, 3399},
		{12, 11, 5377},
		{9, 14, 7479},
		{13, 9, 2298},
		{13, 14, 5859},
		{9, 11, 1951},
		{10, 14, 5533},
		{12, 15, 5318},
		{9, 13, 8212},
		{10, 13, 3904}
	},
//
//	 Test # 6
	{
		{14, 15, 2242},
		{11, 15, 5143},
		{15, 11, 3107},
		{15, 8, 7606},
		{8, 10, 7608},
		{9, 8, 3012},
		{9, 10, 4857},
		{8, 11, 7335},
		{13, 14, 6092},
		{14, 15, 6029},
		{15, 11, 7296},
		{11, 15, 4924},
		{13, 12, 9693},
		{10, 14, 2557},
		{14, 10, 3054},
		{13, 11, 4397},
		{10, 11, 4014},
		{12, 9, 7340},
		{8, 16, 5777}
	},
//
//	 Test # 7
	{
		{16, 9, 2045},
		{16, 8, 1721},
		{8, 12, 1555},
		{11, 15, 4253},
		{9, 8, 8067},
		{9, 11, 6347},
		{8, 12, 2285},
		{10, 14, 8138},
		{12, 15, 6453},
		{14, 16, 8103},
		{12, 9, 6059},
		{10, 14, 9220},
		{8, 14, 5330},
		{16, 13, 3386},
		{9, 10, 5618},
		{13, 8, 5946},
		{10, 11, 8969},
		{9, 15, 1814},
		{13, 11, 5592}
	},
//
//	 Test # 8
	{
		{13, 16, 8531},
		{9, 15, 3647},
		{10, 13, 6816},
		{15, 14, 2222},
		{16, 15, 3620},
		{12, 16, 9254},
		{10, 14, 3677},
		{14, 16, 2539},
		{14, 15, 3849},
		{9, 14, 1520},
		{14, 10, 6053},
		{12, 14, 4052},
		{10, 9, 5328},
		{9, 10, 9453},
		{13, 16, 4153},
		{16, 14, 6879},
		{10, 9, 5781},
		{15, 10, 8719},
		{11, 10, 7945}
	},
//
//	 Test # 9
	{
		{11, 15, 9459},
		{10, 16, 6731},
		{8, 15, 3745},
		{16, 13, 6163},
		{14, 9, 1516},
		{10, 11, 8911},
		{15, 10, 5036},
		{15, 11, 8467},
		{15, 11, 9109},
		{14, 15, 3432},
		{10, 14, 8182},
		{15, 12, 6779},
		{9, 14, 8898},
		{16, 13, 8253},
		{15, 11, 6594},
		{14, 9, 3488},
		{14, 15, 6511},
		{10, 15, 1779},
		{9, 12, 2681}
	},
//
//	 Test # 10
	{
		{9, 13, 9692},
		{14, 10, 5034},
		{9, 11, 7847},
		{11, 14, 1597},
		{9, 11, 8727},
		{8, 11, 3564},
		{10, 11, 2207},
		{12, 10, 7007},
		{10, 14, 4675},
		{15, 12, 2543},
		{16, 9, 4008},
		{11, 13, 2402},
		{14, 13, 5447},
		{15, 9, 6998},
		{16, 11, 2207},
		{16, 14, 2561},
		{12, 16, 3355},
		{16, 11, 4867},
		{13, 12, 6961}
	},
//
//	 Test # 11
	{
		{9, 10, 6475},
		{9, 14, 8560},
		{11, 15, 5070},
		{11, 13, 5659},
		{10, 16, 3798},
		{9, 15, 3555},
		{10, 11, 3818},
		{12, 15, 5864},
		{16, 12, 2962},
		{14, 12, 5006},
		{16, 10, 4939},
		{11, 15, 3782},
		{13, 16, 7711},
		{16, 14, 9255},
		{16, 12, 3121},
		{9, 13, 8278},
		{13, 8, 5559},
		{12, 10, 9051},
		{10, 8, 9562}
	},
//
//	 Test # 12
	{
		{15, 10, 5550},
		{14, 8, 7073},
		{12, 11, 6750},
		{8, 9, 2589},
		{11, 15, 8976},
		{16, 14, 8737},
		{11, 8, 3149},
		{12, 11, 3216},
		{12, 13, 6443},
		{14, 11, 6221},
		{8, 10, 4561},
		{9, 10, 5183},
		{13, 12, 3173},
		{16, 12, 8015},
		{14, 15, 6196},
		{13, 8, 3588},
		{13, 10, 5004},
		{14, 12, 2467},
		{16, 8, 2922}
	},
//
//	 Test # 13
	{
		{10, 16, 1581},
		{12, 13, 6407},
		{16, 13, 8608},
		{9, 14, 5390},
		{15, 8, 8714},
		{12, 16, 8088},
		{11, 15, 3838},
		{15, 8, 2892},
		{16, 8, 2351},
		{8, 16, 8567},
		{8, 13, 8606},
		{11, 12, 2694},
		{10, 16, 9633},
		{11, 14, 5741},
		{11, 15, 4321},
		{11, 12, 3206},
		{12, 13, 9941},
		{13, 14, 4515},
		{11, 13, 3974}
	},
//
//	 Test # 14
	{
		{9, 8, 4814},
		{12, 11, 2673},
		{11, 9, 1568},
		{15, 14, 1632},
		{9, 10, 9098},
		{13, 14, 2130},
		{16, 13, 6405},
		{12, 14, 2530},
		{14, 8, 3138},
		{12, 8, 3002},
		{12, 15, 8230},
		{9, 16, 3146},
		{13, 10, 2057},
		{13, 9, 2925},
		{15, 10, 8774},
		{12, 10, 9731},
		{10, 8, 9707},
		{13, 14, 6329},
		{10, 8, 6656}
	},
//
//	 Test # 15
	{
		{8, 11, 6360},
		{15, 12, 6318},
		{12, 9, 2157},
		{16, 15, 8115},
		{12, 9, 6890},
		{12, 10, 2802},
		{13, 12, 7962},
		{16, 14, 5263},
		{8, 11, 8065},
		{9, 10, 7230},
		{12, 13, 8259},
		{16, 12, 2059},
		{8, 9, 9539},
		{8, 15, 7533},
		{10, 16, 3441},
		{14, 9, 5279},
		{14, 13, 3815},
		{9, 14, 8597},
		{11, 10, 8270}
	},
//
//	 Test # 16
	{
		{14, 13, 2785},
		{14, 8, 8465},
		{11, 16, 1853},
		{14, 13, 3266},
		{12, 14, 5610},
		{15, 16, 5037},
		{11, 10, 4444},
		{13, 8, 3062},
		{12, 16, 3540},
		{15, 12, 2162},
		{10, 9, 7661},
		{15, 10, 2476},
		{9, 8, 6674},
		{13, 14, 2853},
		{10, 9, 5601},
		{10, 13, 5676},
		{10, 16, 3655},
		{15, 11, 2706},
		{9, 8, 6453}
	},
//
//	 Test # 17
	{
		{8, 14, 4818},
		{15, 11, 3096},
		{9, 8, 4054},
		{8, 10, 4304},
		{8, 15, 6646},
		{10, 14, 6574},
		{16, 13, 9232},
		{11, 15, 2994},
		{12, 16, 3963},
		{16, 8, 8242},
		{8, 9, 8270},
		{14, 11, 3319},
		{13, 15, 6803},
		{16, 15, 2028},
		{15, 11, 6163},
		{16, 8, 2990},
		{15, 14, 2037},
		{11, 15, 6039},
		{11, 12, 9410}
	},
//
//	 Test # 18
	{
		{16, 15, 8611},
		{13, 10, 4832},
		{14, 10, 9911},
		{15, 12, 2374},
		{10, 15, 4748},
		{11, 16, 8346},
		{14, 8, 8105},
		{11, 9, 7097},
		{16, 13, 4719},
		{15, 9, 1508},
		{16, 15, 6785},
		{15, 12, 8327},
		{12, 9, 6547},
		{16, 13, 7913},
		{9, 14, 5856},
		{8, 11, 6834},
		{15, 8, 4310},
		{9, 12, 3626},
		{15, 8, 9620}
	},
//
//	 Test # 19
	{
		{8, 12, 5073},
		{9, 10, 4648},
		{9, 11, 8566},
		{10, 13, 3380},
		{11, 9, 3205},
		{16, 8, 1582},
		{12, 16, 7573},
		{13, 12, 2473},
		{13, 16, 1657},
		{12, 11, 7477},
		{8, 16, 3439},
		{14, 13, 7716},
		{11, 9, 3899},
		{11, 13, 5005},
		{9, 12, 5003},
		{8, 13, 5629},
		{16, 12, 9530},
		{14, 9, 8617},
		{16, 11, 2525}
	},
//
//	 Test # 20
	{
		{13, 16, 5863},
		{15, 16, 9434},
		{8, 11, 3450},
		{12, 16, 2577},
		{9, 14, 3608},
		{10, 16, 2444},
		{14, 10, 9338},
		{10, 15, 2623},
		{13, 9, 7340},
		{13, 8, 9442},
		{10, 13, 3697},
		{10, 13, 6915},
		{16, 9, 8529},
		{10, 8, 2971},
		{11, 16, 9429},
		{15, 8, 2060},
		{13, 15, 9547},
		{12, 9, 9461},
		{8, 12, 2713}
	},
//
//	 Test # 21
	{
		{16, 15, 5833},
		{16, 15, 5619},
		{10, 8, 8701},
		{10, 8, 1511},
		{8, 12, 4564},
		{8, 15, 6611},
		{10, 8, 6332},
		{8, 13, 9419},
		{16, 9, 1528},
		{14, 9, 1736},
		{8, 9, 8690},
		{16, 14, 4674},
		{12, 10, 4815},
		{10, 16, 5433},
		{16, 11, 1932},
		{11, 9, 5057},
		{10, 16, 4084},
		{8, 12, 7814},
		{14, 15, 8905}
	},
//
//	 Test # 22
	{
		{15, 12, 7778},
		{14, 16, 3221},
		{15, 12, 2552},
		{15, 13, 5181},
		{15, 16, 9064},
		{8, 15, 7233},
		{10, 15, 7539},
		{16, 15, 2711},
		{12, 15, 1583},
		{16, 12, 4485},
		{8, 16, 4269},
		{15, 10, 4670},
		{8, 9, 4863},
		{14, 16, 2023},
		{15, 16, 7495},
		{10, 12, 2650},
		{10, 14, 7871},
		{16, 14, 7964},
		{10, 11, 7147}
	},
//
//	 Test # 23
	{
		{10, 16, 7053},
		{14, 12, 8542},
		{10, 16, 7939},
		{15, 10, 4331},
		{10, 12, 9399},
		{15, 9, 5238},
		{12, 10, 2800},
		{9, 14, 4590},
		{10, 15, 3807},
		{12, 10, 3418},
		{10, 16, 5373},
		{16, 11, 7970},
		{13, 15, 3226},
		{15, 13, 1687},
		{11, 9, 9427},
		{13, 14, 6760},
		{10, 11, 6250},
		{15, 10, 3481},
		{14, 15, 1600}
	},
//
//	 Test # 24
	{
		{15, 14, 2701},
		{11, 12, 4639},
		{11, 15, 2153},
		{10, 9, 1837},
		{16, 14, 4525},
		{12, 13, 6958},
		{11, 8, 1918},
		{14, 16, 7183},
		{8, 11, 7069},
		{9, 16, 5360},
		{14, 15, 1990},
		{14, 16, 9434},
		{13, 14, 3815},
		{13, 11, 7416},
		{10, 13, 1697},
		{14, 10, 8078},
		{16, 14, 2782},
		{12, 8, 7645},
		{9, 15, 3339}
	},
//
//	 Test # 25
	{
		{12, 16, 5029},
		{12, 11, 3542},
		{11, 13, 9532},
		{13, 16, 2554},
		{9, 11, 8160},
		{8, 16, 5489},
		{9, 13, 2264},
		{13, 9, 9884},
		{12, 15, 9379},
		{16, 14, 6809},
		{8, 16, 3668},
		{8, 9, 6123},
		{10, 8, 4644},
		{16, 8, 6197},
		{15, 11, 3889},
		{11, 10, 3528},
		{14, 8, 7447},
		{12, 14, 1680},
		{8, 16, 7406}
	},
//
//	 Test # 26
	{
		{12, 9, 5084},
		{15, 16, 1742},
		{8, 14, 6146},
		{9, 12, 2616},
		{15, 14, 2390},
		{13, 15, 6307},
		{13, 8, 1991},
		{16, 12, 4061},
		{15, 11, 4622},
		{10, 11, 7894},
		{12, 10, 3647},
		{16, 10, 7109},
		{11, 13, 5348},
		{15, 8, 2692},
		{9, 10, 5627},
		{13, 12, 6827},
		{8, 14, 5143},
		{12, 10, 7423},
		{15, 11, 9102}
	},
//
//	 Test # 27
	{
		{9, 8, 1752},
		{12, 15, 4131},
		{10, 13, 5165},
		{10, 16, 9377},
		{9, 14, 8618},
		{11, 16, 1962},
		{9, 14, 7780},
		{12, 9, 7259},
		{16, 14, 3339},
		{8, 15, 4212},
		{13, 12, 6117},
		{13, 9, 9514},
		{16, 11, 4577},
		{8, 12, 6498},
		{10, 9, 2358},
		{16, 8, 8173},
		{8, 10, 8703},
		{16, 13, 1509},
		{15, 9, 5140}
	},
//
//	 Test # 28
	{
		{10, 16, 9597},
		{14, 15, 4567},
		{15, 9, 7627},
		{16, 11, 5264},
		{16, 8, 5478},
		{11, 9, 3893},
		{16, 15, 6944},
		{12, 14, 6886},
		{9, 8, 5905},
		{8, 13, 4992},
		{11, 8, 9693},
		{14, 11, 2943},
		{12, 13, 2031},
		{11, 14, 1670},
		{9, 14, 2897},
		{12, 15, 8675},
		{9, 15, 7362},
		{11, 8, 4116},
		{10, 12, 6293}
	},
//
//	 Test # 29
	{
		{16, 9, 7616},
		{9, 13, 9933},
		{16, 9, 4928},
		{16, 14, 7176},
		{15, 16, 7812},
		{12, 10, 8971},
		{10, 16, 4367},
		{10, 16, 2861},
		{11, 9, 9956},
		{13, 11, 7744},
		{9, 8, 3412},
		{11, 15, 6191},
		{10, 14, 3803},
		{9, 12, 7626},
		{11, 13, 6647},
		{11, 12, 3192},
		{16, 8, 2547},
		{12, 13, 8238},
		{14, 12, 5414}
	},
//
//	 Test # 30
	{
		{11, 13, 4688},
		{10, 14, 7574},
		{11, 16, 3309},
		{12, 13, 2714},
		{14, 10, 6584},
		{11, 15, 3830},
		{13, 11, 2034},
		{10, 8, 3739},
		{8, 11, 8904},
		{13, 11, 1878},
		{12, 10, 9112},
		{10, 12, 8329},
		{10, 8, 3168},
		{13, 9, 2319},
		{15, 8, 6526},
		{8, 10, 2950},
		{11, 8, 8501},
		{14, 15, 5635},
		{9, 13, 9373}
	},
//
//	 Test # 31
	{
		{9, 15, 3015},
		{14, 16, 7697},
		{13, 14, 6744},
		{14, 9, 9314},
		{11, 13, 4890},
		{11, 9, 4448},
		{12, 14, 4950},
		{10, 15, 2850},
		{8, 13, 6021},
		{16, 13, 3444},
		{14, 8, 6007},
		{15, 11, 9426},
		{9, 10, 5979},
		{9, 15, 4012},
		{12, 10, 3244},
		{15, 12, 8822},
		{16, 14, 3756},
		{8, 12, 5932},
		{16, 13, 2935}
	},
//
//	 Test # 32
	{
		{12, 16, 2131},
		{14, 13, 1688},
		{12, 8, 8837},
		{13, 10, 4107},
		{12, 8, 2738},
		{8, 12, 4491},
		{8, 11, 1759},
		{15, 9, 5693},
		{13, 9, 9837},
		{13, 8, 2981},
		{9, 8, 7542},
		{8, 13, 5479},
		{11, 14, 2987},
		{13, 10, 4965},
		{12, 16, 2859},
		{13, 16, 3206},
		{14, 16, 4072},
		{8, 10, 4682},
		{8, 9, 6154}
	}
};

#endif

Класс!!!

не знаю, стоит ли писать... интересно ли это кому-нибудь. Но хочется "излить душу"...

Ошибка в моей программе особенно обидна тем, что она не в алгоритме, а исключительно в синтаксисе.

Проявляется она в том, что если при начальной обработке набор не удалось упростить (то есть не выбрано и не выкинуто ни одного ключа) - процедура предварительной обработки ошибочно рапортует о найденном решении без ключей и с нулевой ценой :)

А еще это обидно потому, что, после исправления -  именно на таких сложных наборах мой алгоритм мог бы сильнее всего опередить других участников.

вот, для примера посчитал несколько вариантов, на которых в тестах Евгения мой код спасовал:

Это поучительная история о том, что в отладке программ никогда не бывает слишком много тестов. Приходится только удивляться, что мы втроем тусили тут в ветке почти месяц - и за это время никому не пришло в голову попробовать  набор ключей, который не содержит дублей или очевидных кандидатов на вылет. и только когда Евгений сказал об ошибке - я нашел ее буквально за минуты...

Однако, результат есть результат.

Как говорят в футболе, "Красота игры забывается, в истории остается только счет" - кажется Лобановский

Увы, недоотлаженность - эта общая проблема всего современного программного обеспечения. При этом, что с этим делать - никто не знает. Формальные методы накладывают слишком серьезные (неприемлемые) ограничения на язык программирования, а все что остается вне этих рамок - во-первых, приводит к трудозатратам на отладку и тестирование порядка 80-90% от всей стоимости разработки, а во-вторых, совершенно не гарантируют результата.

Еще раз хотелось бы высказать свое восхищение Евгением Петровичем. Во-первых тем, что он, зная, какая предстоит работа, все-таки взялся за этот конкурс, и во-вторых, тем, как он его провел. Собственно, только после публикации результата большинству участников и наблюдателей стало понятно, что работа жюри по своему объему превышает работу всех участников конкурса вместе взятых.

Ну и еще одно наблюдение, имеющее, на мой взгляд, универсальный характер: уровень разработки современного ПО таков, что приходится выбирать только между "правильно, но крайне медленно" и "быстро, но неправильно".

Upd: Да, забыл, что еще, как правило, не обходится и без варианта "медленно и неправильно".

Терпеть не могу эту фразу. Ещё (ровно из той же оперы) не люблю, когда нетренеры цитируют тренерское: "Игрок на площадке должен работать". Мне гораздо больше нравится, когда игроки играют, а не работают. Сравните немцев и бразильцев, чтобы понять о чём я. А Лобановский - он из тех же соображений и договорняки оправдывал: "Не понимаю, почему шахматисты могут согласиться на ничью, а нам нельзя". А о том, что я пришёл на трибуну игру смотреть, а не договорную тухлятину он как-то, видимо, не подумал.

Вообще, "победа любой ценой" - это неспортивно. По мне так Игорь Нетто, сказавший судье о неправильно забитом голе в матче чемпионата мира - великий Спортсмен, а Марадона с его "рукой Господа Бога" просто мячик пинал здорово, но Спортсменом не был.

Только деньги платят за результат, а не за красивую игру. К сожалению.

Не ожидал! Я уже и за темой не следил, думал, что на последнем месте. По факту - моя программа медленнее всех, и если бы не ошибки других участников первого места мне бы не видеть. 

Спасибо организатору конкурса за проделанную работу. Особенно впечатлил подход к подведению итогов .

Евгений Петрович, спасибо!

b707, прокомментируйте пожалуйста свой код, хотя бы кратко.

так всё таки рукой )))
пропустил, не являюсь болельшиком, по мне больше технические виды, спидвей к примеру...
PS эпизод этот помню...

Выкладываю программу с комментариями

// ver 4.6 01-12-20
// Remove sindex
// replace original sizes in spanners for 1,2,3...
// remove all non-needed variables in Size and Spanners

#define MAX_SIZE 160             // максимальный размер ключа в наборе
#define MAX_VARIANTS 8           // максимальное число ключей одного размера
#define NO_INDEX -1

//#define DEBUG

#ifdef DEBUG
#define DEBUG_PRINT(x)     Serial.print(x)
#define DEBUG_PRINTF(x)     Serial.print(F(x))
#define DEBUG_PRINTLN(x)  Serial.println(x)
#define DEBUG_PRINTDEC(x)     Serial.print(x, DEC)

#else
#define DEBUG_PRINT(x)
#define DEBUG_PRINTF(x)
#define DEBUG_PRINTDEC(x)
#define DEBUG_PRINTLN(x)
#endif 
void memRep(uint8_t str, uint8_t level);
void print_span(uint8_t sp, uint8_t* sp_incl);
void print_spans(uint8_t* sp_incl);

#define GET_IND(x)   (x & 0x7F)
#define GET_INCL(x)  ((x & 0x80)>> 7)
#define SET_INCL(x)  (x | 0x80)


/// Spanner class=================
struct Spanner {
	long price;
	uint8_t size1;
	uint8_t size2;
	//int8_t incl;  // - not needed it

/**********/
	Spanner(const uint8_t s1, const uint8_t s2, const long pr, const bool in = false) :
		price(pr), size1(s1), size2(s2) {}

/**********/
	uint8_t get_other_size_for_span(uint8_t fst_size) {
		if (fst_size == size1) return size2;
		return size1;
	}

/**********/
	long get_price() {
		return price;
	}
};
static Spanner spanners[] = {
	{15, 10, 5550},
		{14, 8, 7073},
		{12, 11, 6750},
		{8, 9, 2589},
		{11, 15, 8976},
		{16, 14, 8737},
		{11, 8, 3149},
		{12, 11, 3216},
		{12, 13, 6443},
		{14, 11, 6221},
		{8, 10, 4561},
		{9, 10, 5183},
		{13, 12, 3173},
		{16, 12, 8015},
		{14, 15, 6196},
		{13, 8, 3588},
		{13, 10, 5004},
		{14, 12, 2467},
		{16, 8, 2922}
};


static constexpr uint8_t Span_q = sizeof(spanners) / sizeof(spanners[0]);
uint8_t* size_table;

/// Size class=================
///  Обьект Size 
///  Size выбран если один из ключей с таким размером включен в итоговый набор
/// 
///  span_cnt - пока Size не выбран, span_cnt = числу ключей данного размера
///  если Size выбран, span_cnt = 0
/// 
///  spans - массив номеров ключей, отсортированный по цене от дешевых к дорогим

struct Size {
	uint8_t span_cnt;
	uint8_t spans[MAX_VARIANTS];

	Size(const uint8_t sp) :
		span_cnt(1) {
		spans[0] = sp;
	}

	Size(const Size* ss) :
		span_cnt(ss->span_cnt)
	{
		memcpy(spans, ss->spans, sizeof(spans));
	}

/**********/
	void add_span(const uint8_t sp, uint8_t* sp_incl) {

		long price = spanners[GET_IND(sp_incl[sp])].price;
		uint8_t s = 0;
		while ((s < span_cnt) && (price > spanners[GET_IND(sp_incl[spans[s]])].price)) { s++; }
		for (uint8_t ii = span_cnt; ii > s; ii--) spans[ii] = spans[ii - 1];
		spans[s] = sp;
		span_cnt++;
	}
/**********/
	int8_t replace_span(uint8_t new_sp, uint8_t old_sp) {
		uint8_t sp_num = 0;
		while (spans[sp_num] != old_sp && sp_num < span_cnt) { sp_num++; }
		if (sp_num >= span_cnt) return -1;
		spans[sp_num] = new_sp;
	}
/**********/
	int8_t del_span(uint8_t _sp, uint8_t* sp_incl) {
		uint8_t ii = 0;
		uint8_t sp_num = 0;
		while (spans[sp_num] != _sp && sp_num < span_cnt) { sp_num++; }
		if (sp_num >= span_cnt) return -1;
		for (ii = sp_num + 1; ii < span_cnt; ii++) spans[ii - 1] = spans[ii];
		span_cnt--;

		return span_cnt;
	}
/**********/
	void select_size() {
		span_cnt = 0;
	}
/**********/
	uint8_t lowest_price_span() {
		return spans[0];
	}

};
/// end of Size


// Global variables

Size** sizes;
uint8_t sizes_cnt = 0;

uint8_t* gen_incl;
uint8_t* best_incl;

/************************************************/
// включаем ключ в итоговый набор
/************************************************/
long select_span(const uint8_t _sp, uint8_t* span_incl, Size** s_cur) {
	uint8_t sp = GET_IND(span_incl[_sp]);
#ifdef DEBUG
	print_span(_sp, span_incl);
	DEBUG_PRINT(" selected with price ");
	DEBUG_PRINTLN(spanners[sp].price);
#endif
	span_incl[_sp] = SET_INCL(span_incl[_sp]);
	s_cur[spanners[sp].size1]->select_size();
	s_cur[spanners[sp].size2]->select_size();
	return spanners[sp].price;
}
/************************************************/
// упаковка рабочего списка ключей
// удаляем ключи, ранее помеченные как "лишние"
// передвигаем оставшиеся, чтобы в списке не было пустых мест
/************************************************/
void compact_incl(uint8_t* span_incl, Size** s_cur) {
	uint8_t sp_cnt = span_incl[0];
	while (span_incl[sp_cnt] == 255) sp_cnt--;


	for (uint8_t ii = sp_cnt; ii > 0; ii--) {
		if (span_incl[ii] == 255) {
			if (ii == sp_cnt) { sp_cnt--; continue; }
			if (GET_INCL(span_incl[sp_cnt]) == 0) {
				uint8_t sp = GET_IND(span_incl[sp_cnt]);
				Size* s1 = s_cur[spanners[sp].size1];
				Size* s2 = s_cur[spanners[sp].size2];
				s1->replace_span(ii, sp_cnt);
				s2->replace_span(ii, sp_cnt);
			}
			span_incl[ii] = span_incl[sp_cnt];
			sp_cnt--;
		}
	}
	span_incl[0] = sp_cnt;
}
/************************************************/
// Первоначальная обработка списка ключей
// 
// считаем число уникальных размеров, 
// заменяем реальные размеры на их индексы
// удаляем дубли ключей с высокой ценой
/************************************************/
void count_sizes() {
	uint8_t ii, jj = 0;
	size_table = (uint8_t*)malloc(MAX_SIZE * sizeof(uint8_t));
	int8_t* index = (int8_t*)malloc(MAX_SIZE * sizeof(int8_t));
	uint8_t span_ind[Span_q] = { 0 };
	uint16_t span_sizes[Span_q] = { 0 };
	uint8_t sp_cnt = 0;
	memset(index, NO_INDEX, MAX_SIZE);

	for (ii = 0; ii < Span_q; ii++) {
		uint8_t ss[] = { spanners[ii].size1, spanners[ii].size2 };
		if (ss[1] < ss[0]) {
			ss[1] = ss[0];
			ss[0] = spanners[ii].size2;
		}
		uint16_t sp_size;
		memcpy(&sp_size, ss, 2);

		uint8_t prev_cnt = sizes_cnt;
		for (jj = 0; jj < 2; jj++) {

			if (index[ss[jj]] == NO_INDEX)
			{
				index[ss[jj]] = sizes_cnt;
				size_table[sizes_cnt] = ss[jj];
				sizes_cnt++;
			}

		}

		if (prev_cnt == sizes_cnt) {
			jj = 0;
			while ((span_sizes[jj] != 0) && (span_sizes[jj] != sp_size)) { jj++; }
			if (span_sizes[jj] == sp_size) {
				if (spanners[ii].price < spanners[span_ind[jj]].price) {
					span_ind[jj] = ii;
					spanners[ii].size1 = index[ss[0]];
					spanners[ii].size2 = index[ss[1]];
				}
				continue;
			}
		}
		span_sizes[sp_cnt] = sp_size;
		span_ind[sp_cnt] = ii;
		sp_cnt++;
		spanners[ii].size1 = index[ss[0]];
		spanners[ii].size2 = index[ss[1]];

	}
	free(index);
	realloc(size_table, sizes_cnt);
	gen_incl = (uint8_t*)malloc((sp_cnt + 1) * sizeof(uint8_t));
	best_incl = (uint8_t*)malloc((sp_cnt + 1) * sizeof(uint8_t));
	memcpy(gen_incl + 1, span_ind, sp_cnt);
	gen_incl[0] = sp_cnt;
#ifdef DEBUG
	DEBUG_PRINTF("Span count = ");
	DEBUG_PRINTLN(sp_cnt);
	for (uint8_t k = 0; k < sp_cnt; k++) {
		DEBUG_PRINTF("Span  = ");
		DEBUG_PRINTLN(span_ind[k]);
	}
#endif
}
/************************************************/
// Создание таблицы обьектов Size
// представляем набор ключей как граф
// с вершинами Size и ключами = ребрами
/************************************************/
void create_sizes(uint8_t* sp_incl) {
	uint8_t ii, jj;
	uint8_t sp_cnt = sp_incl[0];
	for (ii = 1; ii < sp_cnt + 1; ii++) {
		uint8_t sp = GET_IND(sp_incl[ii]);
		// ключи с нулевой ценой включаем в итоговый набор автоматически
		if (0 == spanners[sp].get_price()) sp_incl[ii] = SET_INCL(sp_incl[ii]);
		uint8_t ss[] = { spanners[sp].size1, spanners[sp].size2 };
		for (jj = 0; jj < 2; jj++) {
			uint8_t s = ss[jj];
			if (sizes[s] == 0)
			{
				sizes[s] = new Size(ii);
			}
			else {
				sizes[s]->add_span(ii, sp_incl);
			}
		}
	}
	DEBUG_PRINTF("Add sizes ");
	DEBUG_PRINTLN(sizes_cnt);
}
/************************************************/
// Предварительная сортировка графа
/************************************************/

long begin_sort(uint8_t* span_incl, Size** s_cur, long cur_min, long cur_result) {
	bool changed = true;
	DEBUG_PRINT(" enter to begin sort ");
	DEBUG_PRINTLN(cur_result);

	// цикл ниже повторяется до тех пор, пока граф не перестанет меняться
	while (changed) {
		uint8_t sp_cnt = span_incl[0];
		for (uint8_t ii = 0; ii < sizes_cnt; ii++) {

			Size* s1 = s_cur[ii];
    // включаем "очевидные" ключи - размер которых представлен в одном экземпляре
			if (s1->span_cnt == 1) {
				cur_result += select_span(s1->spans[0], span_incl, s_cur);
			}
		}

	// если в какой-то момент цена набранных ключей превысила текущий минимум -
	// останавливаемся, выходим из процедуры и вообще прекращаем поиск в этой итерации
		if (cur_result > cur_min) { DEBUG_PRINTLN(" over value ");return cur_result; }
		changed = false;
		for (uint8_t ii = 1; ii <= sp_cnt; ii++) {

			if (GET_INCL(span_incl[ii]) == 0) {

#ifdef DEBUG
				print_span(ii, span_incl);
				DEBUG_PRINT(" incl ");
				DEBUG_PRINTLN(span_incl[ii]);
#endif
				uint8_t sp = GET_IND(span_incl[ii]);
				Size* s1 = s_cur[spanners[sp].size1];
				Size* s2 = s_cur[spanners[sp].size2];
				// ключи, оба размера которых уже "выбраны"
				// помечаем к удалению
				if ((s1->span_cnt == 0) && (s2->span_cnt == 0)) {
					changed = true;
					span_incl[ii] = 255;
					DEBUG_PRINTLN(" -> del ");
				}
				// ключи, один размер у которых выбран, а другой нет
				
				else if ((s1->span_cnt == 0) != (s2->span_cnt == 0)) {
					Size* s_w = s1;
					if (s1->span_cnt == 0) s_w = s2;
					DEBUG_PRINT(" ii  ");
					DEBUG_PRINT(ii);
					DEBUG_PRINT(" incl ");
					DEBUG_PRINTLN(span_incl[ii]);
					// можно удалить, если это не самый дешевый ключ своего размера
					if (ii != s_w->lowest_price_span()) {
						if (s_w->del_span(ii, span_incl) >= 0) {
							DEBUG_PRINT(" ii -> del  ");
							DEBUG_PRINT(ii);
							changed = true; span_incl[ii] = 255;
						}
					}
				}
			}
		}
		// если что-то изменилось - упаковываем ключи заново
		if (changed) {
			DEBUG_PRINTLN(" compacting ");
			compact_incl(span_incl, s_cur);
		}
	}
	DEBUG_PRINTLN(" exit begin sort ");
	return cur_result;
}
/************************************************/
// проверка, является ли текущий набор полным
// если хоть у одного Size число ключей не равно нулю - значит не полный
// вот тут была ошибка, стоившая мне победы :)
/************************************************/
long test_solution(Size** s_cur) {
	uint8_t ii;
	long jj = 0;
	int8_t factor = 1;

	for (ii = 0; ii < sizes_cnt; ii++) {
		if (s_cur[ii]->span_cnt != 0) {
			factor = -1;
			break;
		}
	}
	
	return (factor);
}

/************************************************/
// копирует список ключей заданной вершины
/************************************************/
uint8_t select_edges2(uint8_t* edges, Size** s_cur, uint8_t st) {
	uint8_t ii, jj = 0;
	Size* s1 = s_cur[st];

	if (s1->span_cnt > 1) {
		for (ii = 0; ii < s1->span_cnt; ii++) { edges[ii] = s1->spans[ii]; }
		return s1->span_cnt;
	}

	return 0;
}
/************************************************/
// поиск "центра" графа методом "срывания листьев" 
/************************************************/
uint8_t find_center(uint8_t* span_incl, Size** s_cur) {

	uint8_t changed = 1;
	uint8_t sp_cnt = span_incl[0];
	// ищем ключи, одна сторона которых выбрана, а другая нет
	// считаем что такие ключи лежат на краях графа (это "листья")
	// удаляем их
	//
	// повторяем, пока граф не перестанет меняться
	while (changed) {
		changed = 0;
		uint8_t changed_sizes[16] = { 0 };
		for (uint8_t ii = 1; ii < sp_cnt + 1; ii++) {

			if (GET_INCL(span_incl[ii]) == 0) {
				uint8_t sp = GET_IND(span_incl[ii]);
				Size* s1 = s_cur[spanners[sp].size1];
				Size* s2 = s_cur[spanners[sp].size2];
				Size* s_w = s1;
				uint8_t sz = spanners[sp].size1;
				
				if ((s1->span_cnt == 0) != (s2->span_cnt == 0)) {
					if (s1->span_cnt == 0) {
						s_w = s2;
						sz = spanners[sp].size2;
					}
					uint8_t del_result = s_w->del_span(ii, span_incl);
					if (del_result > 0) {

						changed_sizes[changed++] = sz;
						span_incl[ii] = 255;
					}
					else if (del_result == 0) {
						DEBUG_PRINTF("Center size for iteration = ");
						DEBUG_PRINTLN(sz);
						return sz;
					}
				}
			}
		}
		for (uint8_t ii = 0; ii < changed; ii++) {
			Size* s1 = s_cur[changed_sizes[ii]];
			s1->span_cnt = 0;
		}
	}
	for (uint8_t ii = 1; ii < sp_cnt + 1; ii++) {
		if (GET_INCL(span_incl[ii]) == 0) {
			uint8_t sp = GET_IND(span_incl[ii]);
			DEBUG_PRINTF("Res size for iteration = ");
			DEBUG_PRINTLN(spanners[sp].size1);
			return spanners[sp].size1;
		}
	}
}


/************************************************/
// очистка временной таблицы размеров
// удаляем обьекты в обратном порядке
// по отношению к порядку из создания 
// для уменьшения фрагментации
/************************************************/
void del_sizes2(Size** dest, Size** source) {
	uint8_t ii, jj;
	for (jj = sizes_cnt; jj > 0; jj--) {
		ii = jj - 1;
		if ((dest[ii] != 0) && (dest[ii] != source[ii])) delete dest[ii];
	}
}
/************************************************/
// инициализация таблицы размеров
/************************************************/
void init_sizes(Size** dest) {
	uint8_t ii;
	for (ii = 0; ii < sizes_cnt; ii++) { dest[ii] = 0; }

}
/************************************************/
// "умное" копирование таблицы размеров для
// очередного шага рекурсии
//
// размеры, которые не будут меняться - передаем ссылкой
// остальным создаем копии
/************************************************/
void cp_sizes3(Size** dest, Size** source) {

	uint8_t ii;
	for (ii = 0; ii < sizes_cnt; ii++) {

		if (source[ii]->span_cnt != 0) {
			if (dest[ii] != 0) *(dest[ii]) = *(source[ii]);
			else dest[ii] = new Size(source[ii]);
		}
		else {
			if ((dest[ii] != 0) && (dest[ii] != source[ii])) delete dest[ii];
			dest[ii] = source[ii];
		}
	}
}
/************************************************/
// основная процедура оптимизации
/************************************************/
long minimum_find(uint8_t* span_incl, Size** s_cur, long cur_min, long cur_result, uint8_t level) {

	// первым делом проверяем, есть ли что оптимизировать
	// или у нас уже полный набор
	level++;
	DEBUG_PRINTF("====  enter to new level ");
	DEBUG_PRINTLN(level);
	bool min_found = false;
	
	int8_t res = test_solution(s_cur);
	if (res > 0) {
		DEBUG_PRINTF("New solution found! min = ");
		DEBUG_PRINTLN(cur_result);
		
		// если найден новый минимум - запоминаем набор ключей
		if (cur_result < cur_min) {
			memcpy(best_incl, span_incl, (span_incl[0] + 1) * sizeof(uint8_t));
			cur_result = cur_result * -1;
		}
		return cur_result;
	}

	// если набор пока не полный
	else {
		DEBUG_PRINTF("non-full set val = ");
		DEBUG_PRINTLN(cur_result);
	// если текущий набор уже дороже ранее найденного минимума - выходим
		if (cur_result >= cur_min) return cur_result;

		DEBUG_PRINTLN("go next");
		
		// создаем массивы для временных копий 
		// массива размеров и массива ключей
		uint8_t k = 0;
		uint8_t* new_s_incl = (uint8_t*)malloc((span_incl[0] + 1) * sizeof(uint8_t));
		if (!new_s_incl) memRep(1, level);
		Size** new_sizes = (Size**)malloc(sizes_cnt * sizeof(Size*));
		if (!new_sizes) memRep(3, level);
		
		// копируем данные во временные массивы
		init_sizes(new_sizes);
		uint8_t new_edges[MAX_VARIANTS] = { 0 };
		// select start size
		memcpy(new_s_incl, span_incl, (span_incl[0] + 1) * sizeof(int8_t));
		cp_sizes3(new_sizes, s_cur);

		// ищем вершину в "центре" оставшейся части графа
		// и создаем список прилегающих к ней ребер (ключей)
		uint8_t start_size = find_center(new_s_incl, new_sizes);
		uint8_t var_cnt = select_edges2(new_edges, s_cur, start_size);
		
		
		// последовательно выбираем по одному ключю из списка
		// начиная с самых дешевых
		// и считаем весь оставшийся граф 
		
		for (k = 0; k < var_cnt; k++) {
			
			// снова копируем размеры и ключи, потому что предыдущая итерация мх "испортила"
			memcpy(new_s_incl, span_incl, (span_incl[0] + 1) * sizeof(int8_t));
			cp_sizes3(new_sizes, s_cur);
			
			// выбираем очередной ключ
			long temp_result = cur_result + select_span(new_edges[k], new_s_incl, new_sizes);
			if (temp_result >= cur_min) break;
			DEBUG_PRINTF("====  new edge at level ");
			DEBUG_PRINTLN(level);
			
			// и прогоняем всю оптимизацию с начала
			temp_result = begin_sort(new_s_incl, new_sizes, cur_min, temp_result);
			if (temp_result > cur_min) continue;
			temp_result = minimum_find(new_s_incl, new_sizes, cur_min, temp_result, level);
			
			
			if ((temp_result < 0) && ((temp_result * -1) < cur_min)) {
				cur_min = temp_result * -1;
				min_found = true;
			}

		}
		if (min_found) {
			cur_result = cur_min * -1;
		}

		del_sizes2(new_sizes, s_cur);
		free(new_sizes);
		free(new_s_incl);
		return cur_result;
	}
}
/************************************************/
// отладочный вывод параметров ключа
void print_span(uint8_t _sp, uint8_t* sp_incl) {
	uint8_t sp = GET_IND(sp_incl[_sp]);
	uint8_t s1 = size_table[spanners[sp].size1];
	uint8_t s2 = size_table[spanners[sp].size2];

	DEBUG_PRINTF("Span  ");
	DEBUG_PRINT(_sp);
	DEBUG_PRINTF(" ");
	DEBUG_PRINT(s1);
	DEBUG_PRINTF("x");
	DEBUG_PRINT(s2);
}
/************************************************/
// печать найденного минимума
/************************************************/
void print_spans(uint8_t* sp_incl) {
	uint8_t ii;
	long jj = 0;
	uint8_t sp_cnt = sp_incl[0];
	//Serial.print(F("Spans in set ="));
	//Serial.print(sp_cnt);
	Serial.println(F("=== Span selection ==="));
	for (ii = 1; ii < sp_cnt + 1; ii++) {
		if (GET_INCL(sp_incl[ii]) > 0) {
			uint8_t sp = GET_IND(sp_incl[ii]);
			uint8_t s1 = size_table[spanners[sp].size1];
			uint8_t s2 = size_table[spanners[sp].size2];
			jj += spanners[sp].price;
			Serial.print("Span  ");
			Serial.print(s1);
			Serial.print("x");
			Serial.println(s2);
		}
	}
	Serial.print(F("Total value = "));
	Serial.println(jj / 100.0, 2);
}
/************************************************/
// отладочное сообщение о проблемах с памятью
/************************************************/
void memRep(uint8_t str, uint8_t level) {
	Serial.print(F("Not enough memory at level "));
	Serial.println(level);
	switch (str) {
	case 1: Serial.println(F("new_incl"));break;
	case 3: Serial.println(F("sizes"));break;
	}
	while (1);
}
/************************************************/
void setup() {
	uint8_t ii;
	long minimum = 0;
	long cur_res = 0;
	Serial.begin(115200);
	while (!Serial) {};
	uint32_t old_mil = micros();

// Первоначальная обработка списка ключей
	count_sizes();
	sizes = (Size**)malloc(sizeof(Size*) * sizes_cnt);
	init_sizes(sizes);


// Создание таблицы обьектов Size
// представляем набор ключей как граф
// с вершинами Size и ключами = ребрами

	create_sizes(gen_incl);
	uint8_t sp_cnt = gen_incl[0];

// считаем полную стоимость всех оставшихся ключей 
// для использования как начальной оценки "минимума"
	for (ii = 1; ii < sp_cnt + 1; ii++) { uint8_t sp = GET_IND(gen_incl[ii]); minimum += spanners[sp].price; }


// Предварительная сортировка графа

	cur_res = begin_sort(gen_incl, sizes, minimum, cur_res);

// основная процедура оптимизации
	minimum = minimum_find(gen_incl, sizes, minimum, cur_res, 0);
	uint32_t tim = micros() - old_mil;
	print_spans(best_incl);
	Serial.print(F("Calculation time = "));
	Serial.print(tim / 1000.0, 3);
	Serial.println(" ms");
}

void loop() {}

При оптимизации наборов ключей я решил трактовать их как граф, где вершинами являются размеры, а ребрами - сами ключи. Причем основная оптимизация делается через работу с вершинами, поэтому первым делом я считаю число уникальных размеров в наборе и создаю табличку вершин, для каждой из которых храню число ребер и их список. Признаком того, что вершина выбрана - является равенство нулю числа ребер на вершине.

Для ключей тоже создаем временную табличку, где храним индекс ключа и флаг, выбран ключ или нет. Первоначально я - по примеру других участников - хранил и признак того, что ключ исключен из набора. Но потом пришел к тому, что исключенные ключи эффективнее просто стирать из таблицы , что уменьшает необходимую память и увеличивает скорость работы.

На этапе создания таблиц так же избавляемся от дублей, оставляя только самые дешевые ключи для заданных комбинаций.

Первоначальная обработка (А) использует те же подходы, что и в алгоритме Андрея.

A.1 - выбираем ключи, размер которых представлен в единственном экземпляре
А.2 - исключаем ключи, лежащие между двумя уже выбранными вершинами
А.3 - находим ключи, один конец которых выбран, а другой нет. Если этот ключ не является самым дешевым для данного размера - его можно выкинуть, более дешевый ключ точно будет выгоднее

Шаги А.1 - А.3 повторяем в цикле до тех пор, пока граф не перестанет меняться. После этого аналитическая часть закончена, переходим к итерациям.

Для начала проверяем, не является ли набор полным, и если да - новым минимумом. Если так - запоминаем найденный набор и выходим из этой итерации.

Алгоритм дальнейшего поиска таков.

(шаг В) Выбираем любую из еще не включенных в набор вершин. Очевидно, что у любой такой вершины как минимум 2 ребра, иначе она была бы уже выбрана. И так же очевидно, что как минимум одно из этих ребер должно войти в оптимальный набор. Все что нам нужно - это посчитать наборы для каждого из этих ребер и сравнить их между собой. Фактически можно сказать. что вся задача упрощается до сравнения двух-трех вариантов ;)...

(шаг С) выбираем любое из ребер данной вершины, считаем его включенным в конечный набор и решаем для полученного набора (который стал чуть меньше) исходную задачу - то есть сначала выполняем шаги А, потом шаг Б и шаг С рекурсивно все глубже и глубже, пока не будет набран полный набор.

Далее поднимаемся обратно до текущего уровня шага С, выбираем следующее ребро и ищем минимум для него. Минимальный из этих наборов и будет глобальным минимумом.

Тут есть некоторые уточнения,  которые помогают сделать поиск эффективнее. На шаге В выгоднее выбирать не любую вершину, а такую, что лежит максимально удаленно от концов графа - тогда при выборе ребра, прилежащего к вершине - на стадии А есть шанс больше упростить граф, чем если вершина крайняя. Для этого используется функция find_center()

И второе - ребра лучше тестировать в порядке возрастания стоимости, тогда есть шанс найти минимальное решение как можно раньше и все остальные ветки просто отсеять, когда, в ходе итерации, их текущая цена превысит найденный минимум.

Остальное - в комментах. Задавайте вопросы.

До этого сам не дошел, а когда Андрей написал п.5:) посчитал не совсем честным включать в свой алгоритм.

Снимаю шляпу!

Время работы моей программы с первого результата  (выложенного впервые в #166) почти не изменилось - на наборе ЕП тогда было 2.8мс, а в текущей версии - 2.53мс. Это потому что основной алгоритм сложился сразу и в дальнейшем я его почти не менял, потратив две недели на борьбу с нехватками памяти.

Насколько я вижу в обсуждении, первый раз о своем "пункте 5" Андрей заговорил лишь спустя 10 дней. Так что мы с ним пришли к этой хитрости независимо.

Это я только о своем коде. Не подумайте плохого:))

я для определенности :)

На самом деле я был очень раздосадован, когда прочитал, что Андрей тоже нашел этот ход :) Потому что этот п5 очень полезная штука :)))

Да, чужой код анализировать это ещё то удовольствие. ) Ещё и когда мало знаешь язык программирования.  Да и принципиально хотел разработать своё решение отличное от других, а не пытался разобраться в других кодах.

Коллеги, получил координаты двух участников, а от b707 ничего нет. Напишите. пожалуйста, чтобы мне на почту один раз ходить, а не несколько.

----------------------------------

Обещанные пояснения к моей программе.

Итак, как уже говорилось - использовались только общие методы, применимые практически для любой переборной задачи, а именно: сначала пытаемся сократить количество перебираемых элементов, удаляя очевидно ненужные, а затем перебираем оставшиеся, используя метод ветвей и границ. Сокращение элементов для перебора делается в три шага.

Итак, первое - удаляем дубликаты. На самом деле для данной задачи это скорее вредно, чем полезно, т.к. вряд ли стоит ожидать, что магазин выложит несколько одинаковых ключей в одном лоте, поэтому это скорее потеря времени, чем его экономия. Но, сказано же - общие методы - делаем. Для удаления дубликатов в строке №143 вызывается функция removeDuplicates(), сама функция находится в строках №№40-49. Первое, что в ней делается - сортировка (стр. №41) по следующим критериям: по первому размеру, если равно, то по второму размеру, если и здесь равенство, то по цене. Всё в порядке возрастания.  Сама по себе сортировка живёт в файле Spanner.h и она совершенно стандартная с использованием стандартной функции qsort, поэтому я на ней не останавливаюсь. В результате сортировки все одинаковые ключи окажутся рядом, причём первым будет идти самый дешёвый. Поэтому, далее мы проходим по получившемуся массиву ключей и помечаем как Spanner::stateDuplicate все элементы, которые не уникальны, кроме первого из группы. Это сделано в строках №№43-46. Функция возвращает количество помеченных ключей.

Далее в строках №№144-146 выполняются некие служебные действия, а именно инициализируются две структуры "решения". Одна для "текущего", а другая для "наилучшего". Им передаётся количество уникальных ключей (которая является верхней оценкой количества ключей в решении, больше не будет). И ( в строке №146) создаётся массив всех имеющихся размеров. Всё это нам пригодятся в будущем.

Второе - находим точно ("железобетонно") входящие в решение ключи и формируем начальное решение из этих ключей. Под "жеоезобетонными" мы понимает те ключи, у которых хотя бы один из размеров больше нигде не встречается. Такой ключ обязан быть в решении, иначе в нём не будет этого размера.

Для этого в строке №148 вызываем функцию markFerroconcretesAndFormSolution (сама функция находится в строках №№70-100). Функция возвращает true, если всё в порядке и false, если не хватило памяти. Как видите я забыл после неё проверить, что она вернула, торопился. Также функция помещает в свой первый параметр (по ссылке) количество таких "железобетонных ключей", которые она нашла. Давайте на неё смотреть.

Для начала она запрашивает массив размеров на максимально возможно количество (строки №№71-75), затем проходит по всему массиву ключей и считает сколько и каких размеров там присутствует. Для этого она для каждого из размеров ключа во-первых, увеличивает счётчик, а во-вторых запоминает в каком именно ключе такой размер встретился (строки №№77-84). Таким образом, после строки №84 в массиве sizesArray мы для каждого размера имеем количество (сколько раз он у нас встречается) и адрес последнего из найденных ключей в котором такой размер встречался.

Ну, осталось только пометить как "железобетонные" те ключи, у которых хотя бы один размер встретился только один раз и добавить их в "базовое решение". Это делается в строках №№87-97. Попутно считается общее количество имеющихся размеров (строки №№ 86 и 90) - оно нам пригодится для оценки полноты найденных решений. Обратите внимание на крайне неудачный комментарий в строке №91 (только сейчас заметил, но поправить уже не могу - ответили). Этот комментарий скрывает очень важный момент. Там ведь проверяется не то, что это дубликат, а то, что ключ не имеет никакого "ненулевого" состояния. Это важно! Если бы мы здесь проверяли только на "дубликат", то ключи у которых оба размера уникальны и больше нигде не встречаются, попадали бы в базовое решение дважды (были бы "дважды железобетонными"), но поскольку мы проверяем на "ненулевое состояние", ключ, который уже помечен как "железобетонный" здесь будет отсеян и второй раз в решение не попадёт.

После завершения формирования базового решения (содержащего только железобетонные ключи), стоит проверить, а не является ли оно полным, т.е. не содержит ли всех размеров? Если так, то нам сильно повезло и ничего больше делать не нужно - оптимальное решение найдено. Такая проверка делается в строке №152. Если же нет, продолжаем работу - строки №№155-162

Наконец, третье - теперь, когда у нас уже есть "базовое решение", содержащее только железобетонные ключи, мы можем проверить все оставшиеся ключи на предмет: а не присутствую ли оба размера данного ключа в базовом решении. Если присутствуют, то такой ключ нам неинтересен - он никак не может попасть в оптимальное решение и мы будем помечать его как бесперспективный. Это делается вызовом функции excludeHopelessSpanners() (строка №155), которая делает всё, о чём говорилось и возвращает количество ключей помеченных как бесперспективные. Сама функция в строках №№106-117 и она достаточно прозрачна и очевидна.

Таким образом, после строки №155 у нас имеется базовое решение, содержащее железобетонные ключи, а все ключи в наборе помечены либо как дубликаты, либо как железобетонные, либо как бесперспективные, либо не помечены никак. Вот именно последние, никак не помеченные, и будут участвовать в переборе. Здесь, для удобства мы ещё раз пересортируем ключи в наборе таким образом, чтобы никак не помеченные ключи оказались в самом начале и при этом были отсортированы по возрастанию цены (это очень важно для применения метода ветвей и границ). Вызов сортировки в строке №158. Сама по себе сортировка, опять же, достаточно проста и очевидна, мы на неё не будем останавливаться. И, наконец, в строке №59, мы запишем в переменную totalSpanners количество оставшихся (никак не помеченных) ключей.

Всё! Мы готовы к перебору. Перебирать будем totalSpanners первых элементов массива spanners.

Перебором занимается функция lookForSolution (строки №№ 122 - 135). Она выполняет перебор методом ветвей и границ, который я подробно описывал в посте #228, поэтому здесь описывать не буду.

На закуску несколько замечаний о сортировке:

1.
при работе со структурированными данными, сортировка - наше всё! Мы применили её дважды, но если бы массивы ключей были большими, то стоило бы применить ещё пару раз, чтобы избавиться от проверок в строках №№ 79, 91 и 110. Т.е. сортировка - главный инструмент в задачах со структурированными данными - она облегчает и ускоряет всё. Да собственно и по жизни, вот прикиньте (особенно в момент, когда чистите снег во дворе или прибираетесь в мастерской), сколько времени своей жизни мы посвящаем перекладыванию предметов с места на место!

2.
Я использую функцию qsort - это хорошая быстрая сортировка, но для маленьких массивов она вполне может проигрывать обычному "пузырьку". Если бы стояла цель выжать всё возможное быстродействие, стоило бы сравнить эти два метода и выбрать лучший для данного случая.

3.
Обычно в задачах, где данных много или они сами по себе большие, никто и никогда не сортирует сам массив данных, как я это делал здесь. Вместо этого заводят массив указателей (на ключи) и сортируют его. Это просто необходимо, когда, например, нам нужно иметь наши данные одновременно отсортированными по разным критериям, или когда наши данные сидят в read-olny памяти и мы не можем их перемещать. Просто заводим столько массивов указателей, сколько критериев, и сортируем эти массивы, а сами данные не трогаем вовсе.

написал

 и некоторые замечания по сортировке

сортировка всех ключей сначала по одному размеру, потом по второму... мне показался такой подход переусложненным. Я преобразую размеры каждого ключа в целое uint16_t, где старший байт это меньший размер, а младший - больший. И потом сравниваю полученное целое с аналогичным индексом для других ключей простым перебором, сразу же выкидывая дубликаты. Возможно, сортировка массива индексов дала бы небольшое ускорение, но эту процедуру надо выполнить всего один раз, да и массивы у нас по определению не больше нескольких десятков ключей...

что касается основного поиска минимума, вы пишете:

Хочу сказать о выделенной фразе. Я в своей программе сознательно отказался от сквозной сортировки всего массива. Как мне кажется... это бессмысленная трата времени. Какой смысл в том, что ключ 12х14 стоит дешевле, чем 22х24 ? - это же разные ключи, они не заменяют друг друга...

Сортировка имеет смысл только среди ключей одного размера. В случае же общих индексов я сначала делал их упорядоченными, а потом от этого отказался и выиграл во времени. Затраты на поддержания порядка в сортированном индексе съедают больше ресурсов, чем дают преимуществ. Вставка элемента в упорядоченный индекс требует поиска верной позиции для вставки и сдвига остальных элементов "ниже". В не сортированный - вы просто добавляете элемент в конец. Тоже самое с удалением - после удаления элемента из середины списка вам придется сдвинуть все остальные на позицию вперед, в несортированном же вы просто перемещаете последний элемент на место удалененого. В среднем любые операции с несортированным списком в N/2 раз быстрее, чем с сортированным. ... за исключением поиска конкретного элемента. Но как раз поиск конкретного ключа в общем индексе нам вообще не требуется...

А ведь и правда, а я при удалении элемента в несортированном массиве сдвигал все последующие друг за другом до конца массива.

Просьба ещё сообщить номер для отслеживания, а то у меня почтальоны ленивые, могут в течении месяца только сообщить, что мене что-то пришло.

Ждём следующий конкурс для профессионалов!!!

Значит Вы не поняли основную идею метода ветвей и границ. Смысл сортировки по цене именно в том, что если какой-то ключ вылез за текущую минимальную цену, то остальные можно не перебирать. Если они не были отсортированы - это бы не работало. Прочитайте ещё раз описание метода, если не поможет, скажите, я сделаю новое с примерами и картинками.

Ну, у нас просто методы разные. При переборе мне не нужно поддерживать порядок в массиве по той простой причине, что я его не нарушаю - я не трогаю массив вообще.

а, ну да... тогда согласен. Идея полного перебора, без предварительного учета размеров, как-то никак не укладывается у меня в голове. Я ее вообще не принимаю в расчет :)  Поэтому и вопросы такие глупые...

Рассказал троим моим знакомым (друзьям, родственникам) о конкурсе, один точно подтвердил, что будет участвовать в будущих конкурсах (контроллеры у него уже есть), два других пока не знаю будут ли, у них ардуиновских наборов нет, но я себе заказал nano every Atmega4808 две штуки (в январе должны прийти), в замен моих находящихся в работе Nano v3.0, так что если что смогу им отдать нанки под конкурс, плюс ещё что потребуется для будущего конкурса из моих запасов, ну если они захотят участвовать.

Дополнение:

Чёт я поторопился заказать Nano Every Atmega4808, пишут фигня ещё та, отменил заказ. Заказал Arduino Nano Every ATMega4809, но одну штуку на пробу.

Очень сомневаюсь в реальности. Большие дяди меряются заковыристыми алгоритмами. А такие алгоритмы демонстрируют свои преимущества при больших наборах данных, что для ардуины проблемно. На малых же наборах они даже перебору данных проигрывают. Глянувши на этот конкурс, видно что более менее продуманный алгоритм у b707 сделан, и он бы порвал 'переборщиков' всех мастей, будь наборы данных побольше и стека ардуины поглубже. А в целом - печалька, даже слона по частям съесть не сумели. Не смотря на ваши мольбы и просьбы )))

Давно бредится в голове идея игры (отдалённо  типа "Core War"), даже пробовал пару раз. Но не получается интересной. Либо слишком сложная, либо слишком простая (с ничейной смертью).