2.6 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4c51000cf542c50ffd7 | Задача 344: Гра "Срібний долар" | 5 | 302003 | 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.
assert.strictEqual(silverDollarGame(), 65579304332);
--seed--
--seed-contents--
function silverDollarGame() {
return true;
}
silverDollarGame();
--solutions--
// solution required