2.7 KiB
id, title, challengeType, forumTopicId, dashedName
| id | title | challengeType | forumTopicId | dashedName |
|---|---|---|---|---|
| 5900f4991000cf542c50ffab | Завдання 301: Нім | 5 | 301955 | 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.
assert.strictEqual(nim(), 2178309);
--seed--
--seed-contents--
function nim() {
return true;
}
nim();
--solutions--
// solution required