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
|
||
```
|