69 lines
2.6 KiB
Markdown
69 lines
2.6 KiB
Markdown
---
|
||
id: 5900f4da1000cf542c50ffed
|
||
title: 'Задача 366: Гра в камені III'
|
||
challengeType: 5
|
||
forumTopicId: 302027
|
||
dashedName: problem-366-stone-game-iii
|
||
---
|
||
|
||
# --description--
|
||
|
||
Два гравці, Антон та Бернхард, грають у наступну гру.
|
||
|
||
Є купка з $n$ каменів.
|
||
|
||
Перший гравець може взяти будь-яку додатню кількість каменів, але не всю купу.
|
||
|
||
Відтак кожен гравець може забрати щонайбільше вдвічі більше каменів, які його противник взяв у попередньому ході.
|
||
|
||
Гравець, який візьме останній камінь, стає переможцем.
|
||
|
||
Наприклад. $n = 5$
|
||
|
||
Якщо перший гравець бере більше одного каменя, наступний гравець зможе забрати все, що залишиться.
|
||
|
||
Якщо перший гравець бере один камінь, залишаючи чотири, і його опонент також візьме один, а отже в підсумку їх буде три.
|
||
|
||
Перший гравець не може забрати всі три, адже він може взяти не більше $2 \times 1 = 2$ каменів. Скажімо, він візьме один камінь — відповідно залишиться 2.
|
||
|
||
Інший гравець, взявши ті два, що залишилися, переможе.
|
||
|
||
Тому 5 — це програшна позиція для першого гравця.
|
||
|
||
Для першого гравця є більше одного можливого кроку для виграшної позиції.
|
||
|
||
Наприклад. якщо $n = 17$, перший гравець може взяти один або чотири камені.
|
||
|
||
Нехай $M(n)$ — максимальна кількість каменів, яку може забрати перший гравець для виграшної позиції за перший крок. тоді $M(n) = 0$ — для будь-якої іншої позиції.
|
||
|
||
$\sum M(n)$ для $n ≤ 100$ — 728.
|
||
|
||
Знайдіть $\sum M(n)$ for $n ≤ {10}^{18}$. Дайте відповідь за модулем ${10}^8$.
|
||
|
||
# --hints--
|
||
|
||
`stoneGameThree()` має повернути `88351299`.
|
||
|
||
```js
|
||
assert.strictEqual(stoneGameThree(), 88351299);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function stoneGameThree() {
|
||
|
||
return true;
|
||
}
|
||
|
||
stoneGameThree();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|