2.2 KiB
2.2 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4fe1000cf542c510010 | Завдання 400: Гра з деревом Фібоначчі | 5 | 302067 | problem-400-fibonacci-tree-game |
--description--
Дерево Фібоначчі - це двійкове дерево, рекурсивно визначене як:
T(0)- це порожнє дерево.T(1)- це двійкове дерево лише з одним вузлом.T(k)складається з кореневого вузла, який маєT(k - 1)іT(k - 2)як дочірній.
Два гравці грають на вибування на такому дереві. Під час кожного ходу гравець вибирає вузол і видаляє цей вузол разом із залежним деревом, що прив'язане до цього вузла. Гравець, якого змушують взяти кореневий вузол усього дерева, програє.
Ось виграшні ходи першого гравця на першому ході за T(k) від k = 1 до k = 6.
Нехай f(k) - це кількість виграшних ходів першого гравця (тобто ходів, для яких другий гравець не має стратегії виграшу) на першому ході гри, коли ця гра проводиться T(k).
Наприклад, f(5) = 1 і f(10) = 17.
Знайдіть f(10000). Вкажіть останні 18 цифр своєї відповіді.
--hints--
fibonacciTreeGame() повинен повернути 438505383468410600.
assert.strictEqual(fibonacciTreeGame(), 438505383468410600);
--seed--
--seed-contents--
function fibonacciTreeGame() {
return true;
}
fibonacciTreeGame();
--solutions--
// solution required