50 lines
2.0 KiB
Markdown
50 lines
2.0 KiB
Markdown
|
---
|
|||
|
|
id: 5900f3d71000cf542c50fee9
|
|||
|
|
title: 'Завдання 106: Особливі суми підмножини: метаналіз'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301730
|
|||
|
|
dashedName: problem-106-special-subset-sums-meta-testing
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Нехай $S(A)$ - сума елементів у наборі A з розміром набору n. Назвемо це спеціальним набором сум, якщо для будь-яких двох не порожніх неперетинних множин В і С, виконуються умови:
|
|||
|
|
|
|||
|
|
1. $S(B) ≠ S(C)$; тобто суми підмножин не можуть бути рівними.
|
|||
|
|
2. Якщо B містить більше елементів, ніж C, то $S(B) > S(C)$.
|
|||
|
|
|
|||
|
|
У цьому завданні, припустимо, що даний набір містить n кількість елементів, що закономірно збільшуються, і для нього справджується друга умова.
|
|||
|
|
|
|||
|
|
Несподівано, що з 25 можливих пар підмножин, які можна отримати з набору, для яких n = 4, лише 1 пару потрібно перевірити на відповідність першій умові. Аналогічно, якщо n = 7, треба перевірити лише 70 з 966 пар підмножин.
|
|||
|
|
|
|||
|
|
Скільки з 261625 можливих пар підмножин треба перевірити на відповідність першій умові, якщо n = 12?
|
|||
|
|
|
|||
|
|
**Примітка:** Це Завдання пов'язане з Завданням 103 та Завданням 105.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`numberRotations()`має повертати`21384`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(subsetSumsMetaTesting(), 21384);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function subsetSumsMetaTesting() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
subsetSumsMetaTesting();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|