62 lines
3.6 KiB
Markdown
62 lines
3.6 KiB
Markdown
---
|
||
id: 5900f5171000cf542c510029
|
||
title: 'Завдання 426: Система коробка-м''яч'
|
||
challengeType: 5
|
||
forumTopicId: 302096
|
||
dashedName: problem-426-box-ball-system
|
||
---
|
||
|
||
# --description--
|
||
|
||
Розглянемо нескінченний ряд коробок. У деяких коробках є м'яч. Наприклад, початкову конфігурацію 2 послідовних заповнених коробок перед 2 порожніми коробками, 2 заповненими коробки, 1 пустою коробкою, і 2 заповненими коробками можна позначити послідовністю (2, 2, 2, 1, 2), у якій по черзі відображається кількість зайнятих і порожніх коробок.
|
||
|
||
Хід складається з переміщення кожного м'яча рівно один раз за наступним правилом: перенесення найлівішого м'яча, котрий не рухали, до найближчої пустої коробки справа.
|
||
|
||
Після одного ходу послідовність (2, 2, 2, 1, 2) стає послідовністю (2, 2, 1, 2, 3) як можна побачити нижче; зверніть увагу, що ми починаємо нову послідовність починаючи з першої заповненої коробки.
|
||
|
||
<img class="img-responsive center-block" alt="анімація показує один завершений хід з (2, 2, 2, 1, 2) до (2, 2, 1, 2, 2, 2, 2, 3)" src="https://cdn.freecodecamp.org/curriculum/project-euler/box-ball-system-1.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Така система називається Системою Box-Ball або якщо коротко BBS.
|
||
|
||
Можна побачити, що після значної кількості ходів система доходить до стану, де послідовні числа заповнених коробок залишаються незмінними. У прикладі нижче послідовні числа зайнятих коробок розвиваються до [1, 2, 3]; ми назвемо це кінцевим станом.
|
||
|
||
<img class="img-responsive center-block" alt="чотири ходи з зайнятих коробок [2, 2, 2] до кінцевого стану [1, 2, 3]" src="https://cdn.freecodecamp.org/curriculum/project-euler/box-ball-system-2.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Ми визначили послідовність $\\{t_i\\}$:
|
||
|
||
$$\begin{align} & s_0 = 290\\,797 \\\\
|
||
& s_{k + 1} = {s_k}^2\bmod 50\\,515\\,093 \\\\ & t_k = (s_k\bmod 64) + 1 \end{align}$$
|
||
|
||
Починаючи з початкової конфігурації $(t_0, t_1, \ldots, t_{10})$, кінцевим станом стане [1, 3, 10, 24, 51, 75].
|
||
|
||
Починаючи з початкової конфігурації $(t_0, t_1, \ldots, t_{10\\,000\\,000})$, знайдіть кінцевий стан.
|
||
|
||
Дайте відповідь як суму квадратів елементів кінцевого стану. Наприклад, якщо кінцевий стан [1, 2, 3], то $14 (= 1^2 + 2^2)$ - ваша відповідь.
|
||
|
||
# --hints--
|
||
|
||
`boxBallSystem()` має вивести `31591886008`.
|
||
|
||
```js
|
||
assert.strictEqual(boxBallSystem(), 31591886008);
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function boxBallSystem() {
|
||
|
||
return true;
|
||
}
|
||
|
||
boxBallSystem();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|