Files
freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/project-euler/problem-103-special-subset-sums-optimum.md

57 lines
2.7 KiB
Markdown
Raw Permalink Normal View History

---
id: 5900f3d61000cf542c50fee7
title: 'Завдання 103: Особливі суми підмножини: оптимізація'
challengeType: 5
forumTopicId: 301727
dashedName: problem-103-special-subset-sums-optimum
---
# --description--
Нехай $S(A)$ показує суму елементів у наборі A з розміром набору n. Назвемо це особливим набором сум, якщо для будь-яких двох не порожніх неперетинних підмножин В і С, виконуються умови:
1. $S(B) ≠ S(C)$; тобто суми підмножин не можуть бути рівними.
2. Якщо В містить більше елементів ніж 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`.
```js
assert.strictEqual(optimumSpecialSumSet(), '20313839404245');
```
# --seed--
## --seed-contents--
```js
function optimumSpecialSumSet() {
return true;
}
optimumSpecialSumSet();
```
# --solutions--
```js
// solution required
```