66 lines
2.2 KiB
Markdown
66 lines
2.2 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4eb1000cf542c50fffd
|
|||
|
|
title: 'Завдання 382: Створення багатокутників'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 302046
|
|||
|
|
dashedName: problem-382-generating-polygons
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Багатокутник - це пласка фігура, що складається з прямих відрізків, які з'єднані таким чином, що формують цільний ланцюг. Багатокутник складається принаймні з трьох сторін та не перетинається.
|
|||
|
|
|
|||
|
|
Множина додатніх чисел $S$ створює багатокутник $P$, якщо:
|
|||
|
|
|
|||
|
|
- немає двох сторін $P$ однакової довжини,
|
|||
|
|
- довжина кожної сторони $P$ знаходиться в $S$, і
|
|||
|
|
- $S$ не містить іншого значення.
|
|||
|
|
|
|||
|
|
Наприклад:
|
|||
|
|
|
|||
|
|
Набір {3, 4, 5} створює багатокутник зі сторонами 3, 4 та 5 (трикутник).
|
|||
|
|
|
|||
|
|
Набір {6, 9, 11, 24} створює багатокутник зі сторонами 6, 9, 11 та 24 (чотирикутник).
|
|||
|
|
|
|||
|
|
Набори {1, 2, 3} і {2, 3, 4, 9} не утворюють жодного багатокутника.
|
|||
|
|
|
|||
|
|
Розглянемо послідовність $s$, визначену наступним чином:
|
|||
|
|
|
|||
|
|
- $s_1 = 1$, $s_2 = 2$, $s_3 = 3$
|
|||
|
|
- $s_n = s_{n - 1} + s_{n - 3}$ для $n > 3$.
|
|||
|
|
|
|||
|
|
Нехай $U_n$ буде набором $\\{s_1, s_2, \ldots, s_n\\}$. Наприклад, $U_{10} = \\{1, 2, 3, 4, 6, 9, 13, 19, 28, 41\\}$.
|
|||
|
|
|
|||
|
|
Нехай $f(n)$ буде числом підмножин $U_n$, що утворює принаймні один багатокутник.
|
|||
|
|
|
|||
|
|
Наприклад, $f(5) = 7$, $f(10) = 501$ та $f(25) = 18\\,635\\,853$.
|
|||
|
|
|
|||
|
|
Знайдіть останні 9 цифр з $f({10}^{18})$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`generatingPolygons()` повинен повертатися як `697003956`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(generatingPolygons(), 697003956);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function generatingPolygons() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
generatingPolygons();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|