Problem 750

Optimal Card Stacking

Card Stacking is a game on a computer starting with an array of $N$ cards labelled $1, 2, \dots, N$ .
A stack of cards can be moved by dragging horizontally with the mouse to another stack but only when the resulting stack is in sequence. The goal of the game is to combine the cards into a single stack using minimal total drag distance.

For the given arrangement of $6$ cards the minimum total distance is $1 + 3 + 1 + 1 + 2 = 8$ .

For $N$ cards, the cards are arranged so that the card at position $n$ is $3^{n} mod (N + 1), 1 \leq n \leq N$ .

We define $G (N)$ to be the minimal total drag distance to arrange these cards into a single sequence.
For example, when $N = 6$ we get the sequence $3, 2, 6, 4, 5, 1$ and $G (6) = 8$ .
You are given $G (16) = 47$ .

Find $G (976)$ .

Note: $G (N)$ is not defined for all values of $N$ .

最优卡牌堆叠

卡牌堆叠是一款电脑游戏，初始状态为 $N$ 张标记有 $1, 2, \dots, N$ 并随机排列的卡牌，每一张卡牌视为一堆。每次行动时，可以将一堆卡牌横向移动到另一堆卡牌上，但移动后组成的新一堆卡牌必须从大到小有序排列。游戏的目标是将所有卡牌合并为一堆，且总的移动距离最小。

对如上图所示的 $6$ 张卡牌，最小总移动距离为 $1 + 3 + 1 + 1 + 2 = 8$ 。

对于 $N$ 张卡牌，我们要求位于第 $n$ 位的卡牌标记为 $3^{n} mod (N + 1), 1 \leq n \leq N$ 。

记 $G (N)$ 为将这些卡牌合并为一堆所需的最小总移动距离。
例如，当 $N = 6$ 时，卡牌标记依次为 $3, 2, 6, 4, 5, 1$ ，因此 $G (6) = 8$ 。
已知 $G (16) = 47$ 。

求 $G (976)$ 。

注：并非所有的 $N$ 都有对应的 $G (N)$ 。