59 lines
2.7 KiB
Markdown
59 lines
2.7 KiB
Markdown
|
---
|
|||
|
|
id: 5900f4991000cf542c50ffab
|
|||
|
|
title: 'Завдання 301: Нім'
|
|||
|
|
challengeType: 5
|
|||
|
|
forumTopicId: 301955
|
|||
|
|
dashedName: problem-301-nim
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# --description--
|
|||
|
|
|
|||
|
|
Nim — це гра з купами каміння, де два гравці по черзі беруть певну кількість каменів із будь-якої купи до поки їх зовсім не залишиться.
|
|||
|
|
|
|||
|
|
Розглянемо звичайну версію Nim на три купки каміння, яка працює наступним чином:
|
|||
|
|
|
|||
|
|
- На початку гри є три купи каменів.
|
|||
|
|
- Коли настає черга певного гравця, він забирає додатне число каменів з будь-якої обраної купи.
|
|||
|
|
- Той, хто першим не зможе зробити хід (тому що не залишилося каменів), програє.
|
|||
|
|
|
|||
|
|
Якщо ($n_1$, $n_2$, $n_3$) вказує на позицію Німа, що складається з купок розміром $n_1$, $n_2$ та $n_3$, тоді з'являється проста функція $X(n_1,n_2,n_3)$, яку можна спробувати знайти або спробувати вирахувати самостійно, яка повертає:
|
|||
|
|
|
|||
|
|
- нуль, якщо гравець, з ідеальною стратегією, що збирається ходити, зрештою програє; чи
|
|||
|
|
- нуль, якщо гравець, з ідеальною стратегією, що збирається ходити, зрештою переможе.
|
|||
|
|
|
|||
|
|
Наприклад, $X(1, 2, 3) = 0$ тому, що дії конкретного гравця неважливі, його опонент може відповісти ходом, відповідно до якого дві купи залишатимуться однакового розміру, адже цей гравець віддзеркалюватиме ходи до поки жодного каменя не залишитися, а тому він програє. Для унаочення:
|
|||
|
|
|
|||
|
|
- поточний гравець ходить (1,2,1)
|
|||
|
|
- опонент ходить (1,0,1)
|
|||
|
|
- поточний гравець ходить (0,0,1)
|
|||
|
|
- хід суперника — (0,0,0), а отже він стає переможцем.
|
|||
|
|
|
|||
|
|
Для скількох додатніх цілих чисел $n ≤ 2^{30}$ відповідає $X(n, 2n, 3n) = 0$?
|
|||
|
|
|
|||
|
|
# --hints--
|
|||
|
|
|
|||
|
|
`nim()` має повернути `2178309`.
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
assert.strictEqual(nim(), 2178309);
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --seed--
|
|||
|
|
|
|||
|
|
## --seed-contents--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
function nim() {
|
|||
|
|
|
|||
|
|
return true;
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
nim();
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
# --solutions--
|
|||
|
|
|
|||
|
|
```js
|
|||
|
|
// solution required
|
|||
|
|
```
|