Задача 750
Оптимальное собирание стопку

"Собирание карт в стопку" - это компьютерная игра, начинающаяся с набора из $N$ карт, пронумерованных $1,2,\ldots,N$. Стопку карт можно переместить, перетягивая ее мышкой в горизонтальном направлении на другую стопку, но только при условии, что в получившейся стопке все карты будут расположены по порядку. Цель игры - собрать все карты в одну стопку, используя минимальное суммарное расстояние перемещений.

Для данного расположения 6 карт минимальное суммарное расстояние равно $1 + 3 + 1 + 1 + 2 = 8$.

$N$ карт изначально расположены так, что карта на позиции $n$ имеет номер $3^n\bmod(N+1), 1\le n\le N$.

Определим $G(N)$ как минимальное суммарное расстояние перемещений, необходимое, чтобы собрать все карты в одну последовательность.
Например, для $N = 6$ мы получим исходное расположение $3,2,6,4,5,1$ и $G(6) = 8$.
Известно, что $G(16) = 47$.

Найдите $G(976)$.

Примечание: $G(N)$ определено не для всех значений $N$.

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