51 lines
2.2 KiB
Markdown
51 lines
2.2 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4b11000cf542c50ffc4
|
|||
|
|
title: 'Завдання 325: Гра в камені II'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301982
|
|||
|
|
dashedName: problem-325-stone-game-ii
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Для гри необхідно три купи камінців та два гравці. На кожному ході гравець видаляє кілька каменів із купи. Кількість видалень каміння має бути додатним і кратним кількості камінців в меншій купі.
|
|||
|
|
|
|||
|
|
Наприклад, нехай введена пара (6,14) означає, що в меншій купі 6 каменів, а в більшій – 14, тоді перший гравець може видалити 6 або 12 каменів з більшої кулі.
|
|||
|
|
|
|||
|
|
Гравець, що забере всі камені з купи – перемагає.
|
|||
|
|
|
|||
|
|
Виграшною конфігурацією є та, де перший гравець може виграти. Наприклад, (1,5), (2,6) і (3,12) виграшні конфігурації, тому що перший гравець одразу прибирає всі камені у другій купі.
|
|||
|
|
|
|||
|
|
Програшною є конфігурація, коли другий гравець може виграти, незалежно від того, що робить перший гравець. Наприклад, (2,3) і (3,4) програшні конфігурації: будь-який хід залишає можливість виграти для другого гравця.
|
|||
|
|
|
|||
|
|
Визначте $S(N)$ як суму ($x_i + y_i$) для усіх програшних конфігурацій ($x_i$, $y_i$), $0 < x_i < y_i ≤ N$. Ми можемо перевірити, що $S(10) = 211$ та $S({10}^4) = 230\\,312\\,207\\,313$.
|
|||
|
|
|
|||
|
|
Знайдіть $S({10}^{16})\bmod 7^{10}$.
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`stoneGameTwo()` має повернути `54672965`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(stoneGameTwo(), 54672965);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function stoneGameTwo() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
stoneGameTwo();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|