freeCodeCamp/curriculum/challenges/ukrainian/10-coding-interview-prep/project-euler/problem-382-generating-polygons.md

id, title, challengeType, forumTopicId, dashedName

id	title	challengeType	forumTopicId	dashedName
5900f4eb1000cf542c50fffd	Завдання 382: Створення багатокутників	5	302046	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.

assert.strictEqual(generatingPolygons(), 697003956);

--seed--

--seed-contents--

function generatingPolygons() {

  return true;
}

generatingPolygons();

--solutions--

// solution required