57 lines
2.6 KiB
Markdown
57 lines
2.6 KiB
Markdown
---
|
||
id: 5900f4c51000cf542c50ffd7
|
||
title: 'Задача 344: Гра "Срібний долар"'
|
||
challengeType: 5
|
||
forumTopicId: 302003
|
||
dashedName: problem-344-silver-dollar-game
|
||
---
|
||
|
||
# --description--
|
||
|
||
Один з варіантів N.G. Гру де Брейна "Срібний долар" можна описати таким чином:
|
||
|
||
В рядку квадратів розміщена певна кількість монет, щонайбільше одна на квадрат. Цінність має лише монета під назвою "срібний долар". Двоє гравців ходять по черзі. Хід може бути або звичайним, або спеціальним.
|
||
|
||
Звичайний хід полягає в тому, щоб вибрати одну монету і перемістити її на один чи два квадрати ліворуч. Монета не може вийти за межі смуги або накрити собою іншу монету.
|
||
|
||
Крім того, замість звичайного ходу, гравець може обрати спеціальний, а саме - забрати крайню ліву монету. Якщо звичайний рух неможливий, гравець не має вибору, окрім як забрати крайню ліву монету.
|
||
|
||
Переможець - гравець, який забирає срібний долар.
|
||
|
||
<img class="img-responsive center-block" alt="Гра "Срібний долар"" src="https://cdn.freecodecamp.org/curriculum/project-euler/silver-dollar-game.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Виграшна конфігурація полягає в розташуванні монет таким чином, щоб перший гравець зміг перемогти незалежно від дій другого гравця.
|
||
|
||
Нехай $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
|
||
```
|