55 lines
2.2 KiB
Markdown
55 lines
2.2 KiB
Markdown
---
|
||
id: 5900f4fe1000cf542c510010
|
||
title: 'Завдання 400: Гра з деревом Фібоначчі'
|
||
challengeType: 5
|
||
forumTopicId: 302067
|
||
dashedName: problem-400-fibonacci-tree-game
|
||
---
|
||
|
||
# --description--
|
||
|
||
Дерево Фібоначчі - це двійкове дерево, рекурсивно визначене як:
|
||
|
||
- $T(0)$ - це порожнє дерево.
|
||
- $T(1)$ - це двійкове дерево лише з одним вузлом.
|
||
- $T(k)$ складається з кореневого вузла, який має $T(k - 1)$ і $T(k - 2)$ як дочірній.
|
||
|
||
Два гравці грають на вибування на такому дереві. Під час кожного ходу гравець вибирає вузол і видаляє цей вузол разом із залежним деревом, що прив'язане до цього вузла. Гравець, якого змушують взяти кореневий вузол усього дерева, програє.
|
||
|
||
Ось виграшні ходи першого гравця на першому ході за $T(k)$ від $k = 1$ до $k = 6$.
|
||
|
||
<img class="img-responsive center-block" alt="виграшні ходи першого гравця, на першому ході за k = 1 до k = 6" src="https://cdn.freecodecamp.org/curriculum/project-euler/fibonacci-tree-game.png" style="background-color: white; padding: 10px;" />
|
||
|
||
Нехай $f(k)$ - це кількість виграшних ходів першого гравця (тобто ходів, для яких другий гравець не має стратегії виграшу) на першому ході гри, коли ця гра проводиться $T(k)$.
|
||
|
||
Наприклад, $f(5) = 1$ і $f(10) = 17$.
|
||
|
||
Знайдіть $f(10000)$. Вкажіть останні 18 цифр своєї відповіді.
|
||
|
||
# --hints--
|
||
|
||
`fibonacciTreeGame()` повинен повернути `438505383468410600`.
|
||
|
||
```js
|
||
assert.strictEqual(fibonacciTreeGame(), 438505383468410600);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function fibonacciTreeGame() {
|
||
|
||
return true;
|
||
}
|
||
|
||
fibonacciTreeGame();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|