Задача 524
Первая сортировка II

Рассмотрим следующий алгоритм сортировки списка чисел по возрастанию:

  • 1. Последовательно проверить каждую пару соседних элементов, начиная с первых двух.
  • 2. Если элементы пары расположены в неправильном порядке:
    • a. Переместить меньший элемент пары в начало списка.
    • b. Начать снова с шага 1.
  • 3. Если все пары имеют правильный порядок, остановиться.

Например, список { 4 1 3 2 } будет отсортирован следующим образом:

  • 4 1 3 2 (4 и 1 в неправильном порядке, 1 перемещается в начало списка)
  • 1 4 3 2 (4 и 3 в неправильном порядке, 3 перемещается в начало списка)
  • 3 1 4 2 (3 и 1 в неправильном порядке, 1 перемещается в начало списка)
  • 1 3 4 2 (4 и 2 в неправильном порядке, 2 перемещается в начало списка)
  • 2 1 3 4 (2 и 1 в неправильном порядке, 1 перемещается в начало списка)
  • 1 2 3 4 (список отсортирован)

Пусть F(L) будет количеством исполнений шага 2a в процессе сортировки списка L. Например, F({ 4 1 3 2 }) = 5.

Мы можем перечислить все перестановки P целых чисел {1, 2, ..., n} в лексикографическом порядке и присвоить каждой перестановке индекс In(P) от 1 до n!, соответствующий ее положению в получившемся списке.

Пусть Q(n, k) = min(In(P)) для F(P) = k будет индексом первой перестановки, требующей ровно k шагов для сортировки списка алгоритмом "первая сортировка". Если не существует такой перестановки, для которой F(P) = k, то значение Q(n, k) не определено.

Для n = 4 имеем:

PI4(P)F(P)
{1, 2, 3, 4}10Q(4, 0) = 1
{1, 2, 4, 3}24Q(4, 4) = 2
{1, 3, 2, 4}32Q(4, 2) = 3
{1, 3, 4, 2}42
{1, 4, 2, 3}56Q(4, 6) = 5
{1, 4, 3, 2}64
{2, 1, 3, 4}71Q(4, 1) = 7
{2, 1, 4, 3}85Q(4, 5) = 8
{2, 3, 1, 4}91
{2, 3, 4, 1}101
{2, 4, 1, 3}115
{2, 4, 3, 1}123Q(4, 3) = 12
{3, 1, 2, 4}133
{3, 1, 4, 2}143
{3, 2, 1, 4}152
{3, 2, 4, 1}162
{3, 4, 1, 2}173
{3, 4, 2, 1}182
{4, 1, 2, 3}197Q(4, 7) = 19
{4, 1, 3, 2}205
{4, 2, 1, 3}216
{4, 2, 3, 1}224
{4, 3, 1, 2}234
{4, 3, 2, 1}243

Пусть R(k) = min(Q(n, k)) для всех n, для которых значение Q(n, k) определено.

Найдите R(1212).

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