59 lines
2.3 KiB
Markdown
59 lines
2.3 KiB
Markdown
---
|
||
id: 5900f4361000cf542c50ff48
|
||
title: 'Завдання 201: Підмножини з унікальною сумою'
|
||
challengeType: 5
|
||
forumTopicId: 301841
|
||
dashedName: problem-201-subsets-with-a-unique-sum
|
||
---
|
||
|
||
# --description--
|
||
|
||
Для будь-якого набору чисел $A$ нехай $sum(A)$ буде сумою елементів $A$.
|
||
|
||
Розглянемо набір $B = \\{1,3,6,8,10,11\\}$. Існує 20 підмножин $B$, що містять три елементи, і їх сумидорівнюють:
|
||
|
||
$$\begin{align} & sum(\\{1,3,6\\}) = 10 \\\\
|
||
& sum(\\{1,3,8\\}) = 12 \\\\ & sum(\\{1,3,10\\}) = 14 \\\\
|
||
& sum(\\{1,3,11\\}) = 15 \\\\ & sum(\\{1,6,8\\}) = 15 \\\\
|
||
& sum(\\{1,6,10\\}) = 17 \\\\ & sum(\\{1,6,11\\}) = 18 \\\\
|
||
& sum(\\{1,8,10\\}) = 19 \\\\ & sum(\\{1,8,11\\}) = 20 \\\\
|
||
& sum(\\{1,10,11\\}) = 22 \\\\ & sum(\\{3,6,8\\}) = 17 \\\\
|
||
& sum(\\{3,6,10\\}) = 19 \\\\ & sum(\\{3,6,11\\}) = 20 \\\\
|
||
& sum(\\{3,8,10\\}) = 21 \\\\ & sum(\\{3,8,11\\}) = 22 \\\\
|
||
& sum(\\{3,10,11\\}) = 24 \\\\ & sum(\\{6,8,10\\}) = 24 \\\\
|
||
& sum(\\{6,8,11\\}) = 25 \\\\ & sum(\\{6,10,11\\}) = 27 \\\\
|
||
& sum(\\{8,10,11\\}) = 29 \\end{align}$$
|
||
|
||
Деякі з цих сум трапляються більше, ніж один раз, інші - унікальні. Для набору $A$ нехай $U(A,k)$ буде набором унікальних сум $k$-елементних підмножин $A$, у нашому прикладі ми знаходимо $U(B,3) = \\{10,12,14,18,21,25,27,29\\}$ і $sum(U(B,3)) = 156$.
|
||
|
||
Тепер розглянемо $100$-елементний набір $S = \\ {1^2, 2^2, \ldots, {100}^2\\}$. $S$ має $100\\,891\\,344\\,545\\,564\\,193\\,3\\,812\\,497\\,256\\;$ $50$-елементних підмножин.
|
||
|
||
Визначте суму всіх цілих чисел, які є сумою лише одного з $50$-елементів підмножини $S$, тобто знайдіть $sum (U(S,50))$.
|
||
|
||
# --hints--
|
||
|
||
`uniqueSubsetsSum()` має видати `115039000`.
|
||
|
||
```js
|
||
assert.strictEqual(uniqueSubsetsSum(), 115039000);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function uniqueSubsetsSum() {
|
||
|
||
return true;
|
||
}
|
||
|
||
uniqueSubsetsSum();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|