59 lines
3.4 KiB
Markdown
59 lines
3.4 KiB
Markdown
---
|
||
id: 5900f4bd1000cf542c50ffcf
|
||
title: 'Задача 336: Послідовність Максімікс (Maximix Arrangements)'
|
||
challengeType: 5
|
||
forumTopicId: 301994
|
||
dashedName: problem-336-maximix-arrangements
|
||
---
|
||
|
||
# --description--
|
||
|
||
Потяг возить чотири вагони, у порядку: $ABCD$. Проте, інколи, коли потяг прибуває, щоб причепити вагони, вони стоять у неправильному порядку.
|
||
|
||
Щоб переставити вагони, їх усі ставлять на велике коло, що обертається. Після того, як вагони роз'єднуються у певний момент, потяг рухається з кола разом с вагонами, що до нього приєднані. Вагони, що залишилися, розвертаються на 180°. Після цього, усі вагони з'єднуються, і цей процес повторюється стільки разів, скільки необхідно для того, щоб отримати найменшу кількість обертів кола.
|
||
|
||
Деякі послідовності, як $ADCB$, можуть легко бути вирішені: вагони роз'єднуються між $A$ і $D$, а після того, як $DCB$ повертається, досягнуто правильну послідовність.
|
||
|
||
Проте, Саймон Простачок, водій потяга, не надто відомий своєю кмітливістю, завжди вирішує цю проблему, спочатку виставляючи вагон $A$ на правильну позицію, потім вагон $B$, і так далі.
|
||
|
||
Якщо взяти 4 вагони, найгірші можливі варіації для Саймона, які ми назвемо послідовностями Максімікс, це $DACB$ і $DBAC$; кожна з яких вимагатиме від нього 5 обертів (хоча, якби використовувати найбільш оптимальний підхід, їх можна було б вирішити лише за 3 оберти). Нижче наведено те, як він вирішуватиме $DACB$.
|
||
|
||
<img class="img-responsive center-block" alt="5 обертів для послідовності максімікс DACB" src="https://cdn.freecodecamp.org/curriculum/project-euler/maximix-arrangements.gif" style="background-color: white; padding: 10px;" />
|
||
|
||
Можна визначити, що існує 24 послідовності максімікс для 6-ти вагонів, з яких десята лексикографічна послідовність - це $DFAECB$.
|
||
|
||
Знайдіть лексикографічну послідовність максімікс ${2011}^{\text{th}}$ для 11 вагонів.
|
||
|
||
# --hints--
|
||
|
||
`maximixArrangements()` має повернути рядок.
|
||
|
||
```js
|
||
assert(typeof maximixArrangements() === 'string');
|
||
```
|
||
|
||
`maximixArrangements()` має повернути рядок `CAGBIHEFJDK`.
|
||
|
||
```js
|
||
assert.strictEqual(maximixArrangements(), 'CAGBIHEFJDK');
|
||
```
|
||
|
||
# --seed--
|
||
|
||
## --seed-contents--
|
||
|
||
```js
|
||
function maximixArrangements() {
|
||
|
||
return true;
|
||
}
|
||
|
||
maximixArrangements();
|
||
```
|
||
|
||
# --solutions--
|
||
|
||
```js
|
||
// solution required
|
||
```
|