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