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
|
|||
|
|
```
|