Задача 336
Расстановки максимикса

Обычно к локомотиву прицепляют четыре вагона в следующем порядке: ABCD. Однако, бывает так, что когда локомотив прибывает за вагонами, они расположены в неправильном порядке.
Для того, чтобы поменять порядок вагонов, они помещаются на большую поворотную платформу. После того, как вагоны были расцеплены в опрделенной точке, состав из оставшихся вагонов и локомотива отъезжает от поворотной платформы. Оставшиеся на платформе вагоны разворачиваются на 180 градусов. После этого, все вагоны вновь сцепляют вместе и процесс повторяется столько раз, сколько потребуется. При этом необходимо достичь наименьшего числа использований поворотной платформы.
Некоторые расстановки вагонов, такие как ADCB, могут быть легко решены: вагоны разделяются в точке между A и D, а после поворота вагонов DCB соединяются вновь. Получен правильный порядок следования.

Тем не менее, Простой Саймон, машинист локомотива, не отличается эффективностью, поэтому он всегда решает проблему иначе: сперва он прицепляет вагон А, затем - вагон В, и т.д.

В случае с четырьмя вагонами, наихудшими возможными для Саймона их расположениями, которые будем называть расстановками максимикса, являются DACB и DBAC. В случае каждой из них потребуются пять поворотов (в то же время, при решении более эффективным подходом, этого можно было бы достичь тремя поворотами). Этот процесс показан ниже для случая расстановки вагонов в порядке DACB.

Можно показать, что для шести вагонов всего существует 24 расстановки максимикса. Среди них десятой словарной (лексикографической) расстановкой максимикса является DFAECB.

Определите 2011-ую словарную расстановку максимикса для случая с 11 вагонами.

Оригинал
 
© Проект Эйлера | Translated problems from ProjectEuler.net