55 lines
2.5 KiB
Markdown
55 lines
2.5 KiB
Markdown
---
|
||
id: 5900f49f1000cf542c50ffb1
|
||
title: 'Проблема 306: Гра з паперовими стрічками'
|
||
challengeType: 5
|
||
forumTopicId: 301960
|
||
dashedName: problem-306-paper-strip-game
|
||
---
|
||
|
||
# --description--
|
||
|
||
Наведена нижче гра є класичним прикладом Теорії комбінаторіальної гри:
|
||
|
||
Двоє гравців починають з смужки $n$ білих квадратів і почергово ходять. Під час кожного ходу, гравець вибирає два суміжних білих квадратики і розмальовує їх у чорний колір. Перший гравець, який не може зробити хід - програє.
|
||
|
||
- $n = 1$: Немає дійсних кроків, тому перший гравець автоматично програє.
|
||
- $n = 2$: Лише один дійсний крок, після якого другий гравець програє.
|
||
- $n = 3$: два дійсні кроки, але обидва залишають положення, де другий гравець програє.
|
||
- $n = 4$: Є три дійсні кроки для першого гравця; який може виграти гру замалювавши два середніх квадрати.
|
||
- $n = 5$: чотири дійсні кроки для першого гравця (показано нижче червоним кольором); але незважаючи на те, що буде робити гравець, другий гравець (синій) виграє.
|
||
|
||
<img class="img-responsive center-block" alt="дійсний початок ходів для смужки на 5 квадратів" src="https://cdn.freecodecamp.org/curriculum/project-euler/paper-strip-game.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Тому за $1 ≤ n ≤ 5$, є 3 значення $n$, для яких перший гравець може прийти до виграшу.
|
||
|
||
Тому за $1 ≤ n ≤ 50$, є 40 значень $n$, для яких перший гравець може прийти до виграшу.
|
||
|
||
Що за $1 ≤ 1\\,000\\,000$, скільки значень $n$ для чого перший гравець може виграти?
|
||
|
||
# --hints--
|
||
|
||
`paperStripGame()` має повернути `852938`.
|
||
|
||
```js
|
||
assert.strictEqual(paperStripGame(), 852938);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function paperStripGame() {
|
||
|
||
return true;
|
||
}
|
||
|
||
paperStripGame();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|