Задача 103
Суммы особых подмножеств: оптимум

Пусть S(A) представляет собой сумму элементов множества А размером n. Будем называть это множество особым суммарным множеством, если для любых двух непустых и непересекающихся подмножеств B и C справедливо следующее:

  1. S(B) ≠ S(C); т.е. суммы элементов подмножеств не могут быть равными.
  2. Если B содержит больше элементов, чем C, то S(B) > S(C).

Если минимизировать сумму S(A) при заданном значении n, получим оптимальное особое суммарное множество. Ниже даны первые пять оптимальных особых суммарных множеств.

n = 1: {1}
n = 2: {1, 2}
n = 3: {2, 3, 4}
n = 4: {3, 5, 6, 7}
n = 5: {6, 9, 11, 12, 13}

Похоже на то, что для заданного оптимального множества A = {a_(1), a_(2), ... , a_(n)}, следующим оптимальным множеством будет множество вида B = {b, a_(1)+b, a_(2)+b, ... ,a_(n)+b}, где b - "средний" элемент предыдущей строки.

Применяя данное "правило", можно было бы ожидать, что оптимальным множеством при n = 6 станет A = {11, 17, 20, 22, 23, 24}, у которого S(A) = 117. Однако, данное множество не является оптимальным, поскольку мы всего-лишь применили алгоритм нахождения близкого к оптимальному множества. Оптимальным множеством при for n = 6 будет A = {11, 18, 19, 20, 22, 25}, у которого S(A) = 115. Этому множеству соответствует строка 111819202225.

Дано, что A является оптимальным особым суммарным множеством при n = 7. Найдите строку, соответствующую этому множеству.

Примечание: Данная задача имеет также отношение к задачам №105 и №106.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net