--- id: 5900f4c51000cf542c50ffd7 title: 'Задача 344: Гра "Срібний долар"' challengeType: 5 forumTopicId: 302003 dashedName: problem-344-silver-dollar-game --- # --description-- Один з варіантів N.G. Гру де Брейна "Срібний долар" можна описати таким чином: В рядку квадратів розміщена певна кількість монет, щонайбільше одна на квадрат. Цінність має лише монета під назвою "срібний долар". Двоє гравців ходять по черзі. Хід може бути або звичайним, або спеціальним. Звичайний хід полягає в тому, щоб вибрати одну монету і перемістити її на один чи два квадрати ліворуч. Монета не може вийти за межі смуги або накрити собою іншу монету. Крім того, замість звичайного ходу, гравець може обрати спеціальний, а саме - забрати крайню ліву монету. Якщо звичайний рух неможливий, гравець не має вибору, окрім як забрати крайню ліву монету. Переможець - гравець, який забирає срібний долар. Гра "Срібний долар" Виграшна конфігурація полягає в розташуванні монет таким чином, щоб перший гравець зміг перемогти незалежно від дій другого гравця. Нехай $W(n, c)$ буде кількістю виграшних конфігурацій у рядку на $n$ квадратів, $c$ монет і один срібний долар. Дано, що $W(10, 2) = 324$ та $W(100, 10) = 1\\,514\\,7046\\,113\\,500$. Знайти $W(1\\,000\\,000, 100)$ відповідь до модулю з семіпрієм $1000\\,036\\,000\\,099 (= 1\\,000\\,003 \tстворив 1\\,000\\,000\\,033)$. # --hints-- `silverDollarGame()` повертає `65579304332`. ```js assert.strictEqual(silverDollarGame(), 65579304332); ``` # --seed-- ## --seed-contents-- ```js function silverDollarGame() { return true; } silverDollarGame(); ``` # --solutions-- ```js // solution required ```