57 lines
2.7 KiB
Markdown
57 lines
2.7 KiB
Markdown
---
|
||
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
|
||
```
|