2.7 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f3d61000cf542c50fee7 | Завдання 103: Особливі суми підмножини: оптимізація | 5 | 301727 | problem-103-special-subset-sums-optimum |
--description--
Нехай S(A) показує суму елементів у наборі A з розміром набору n. Назвемо це особливим набором сум, якщо для будь-яких двох не порожніх неперетинних підмножин В і С, виконуються умови:
S(B) ≠ S(C); тобто суми підмножин не можуть бути рівними.- Якщо В містить більше елементів ніж C, тоді
S(B) > S(C).
Якщо S(A) обмежене даним n, назвемо його оптимальним набором особливих сум. Перші п'ять оптимальних особливих сум наведені нижче.
$\begin{align} & n = 1: \{1\} \\ & n = 2: \{1, 2\} \ & n = 3: \{2, 3, 3, 4\} \\ & n = 4: \{3, 5, 6, 7\} \\ & n = 5: \{6, 9, 11, 12, 13\} \\ \end{align}$$
Здається, що для даного оптимального набору A = \\{a_1, a_2, \ldots, a_n\\}, наступний оптимальний набір у вигляді B = \\{b, a_1 + b, a_2 + b, \ldots, a_n + b\\}, де b - середній елемент з попереднього рядка.
Застосувавши цю "умову", очікуємо такий оптимальний набір для n = 6 буде A = \\{11, 17, 20, 22, 23, 24\\}, з S(А) = 117. Однак, це не набір оптимальних множин, оскільки ми просто застосували алгоритм для забезпечення майже оптимального набору. Для n = 6 оптимальний набір - A = \\{11, 18, 19, 20, 22, 25\\}, з S(A) = 115 та відповідний рядок у наборі: 111819202225.
Якщо відомо, що А є оптимальною спеціальною сумою, заданою для n = 7, знайдіть її в рядку.
Примітка: Це завдання пов'язане із завданнями 105 та 106.
--hints--
optimumSpecialSumSet() повинен повернути рядок 20313839404245.
assert.strictEqual(optimumSpecialSumSet(), '20313839404245');
--seed--
--seed-contents--
function optimumSpecialSumSet() {
return true;
}
optimumSpecialSumSet();
--solutions--
// solution required