2.6 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4da1000cf542c50ffed | Задача 366: Гра в камені III | 5 | 302027 | 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.
assert.strictEqual(stoneGameThree(), 88351299);
--seed--
--seed-contents--
function stoneGameThree() {
return true;
}
stoneGameThree();
--solutions--
// solution required