logo AlgoBeat OnlineJudge
登录 注册

#101840. [BZOJ 1840] Zju1742 Gap

内存限制:64 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目背景

一起来玩一个叫 Gap 的游戏吧!

你有 张双标号的牌,第一个标号代表牌的花色(从 ),第二个标号代表牌的大小(从 )。

一开始,你打乱这些牌并把他们重新摆成 列的方阵,再在每一行最左侧加入一个空位,如下图:

接着,你拿走所有大小为 的牌,并把他们按花色顺序放在最左侧的空位上( 在第一行,48284$ 个空,如下图。

你可以做任意次移动:选择一个空位,把它左边的牌的后继移动到这个空位上。如果这个空位左边也是空位,或者左边的牌没有后继,那么无法移动。

后继的定义是同花色的牌中,大小比当前牌要大的牌中的最小的牌。如: 的后继是 没有后继。

在上面的例子中,你可以把 移动到 右边的空位中,或者把 移动到 右边的空位中。

这个游戏的目标是通过若干次操作,把每个花色的牌都放在同一行,如下图:

你需要通过最少的步数达成这个目标,输出最小的步数。

输入格式

列,表示初始状态。

输出格式

一个数表示答案,如果无解则输出

注意,输出的步数不包含一开始把一号牌放在最左边的步数。

样例

样例输入 #1

26 31 13 44 21 24 42 
17 45 23 25 41 36 11 
46 34 14 12 37 32 47 
16 43 27 35 22 33 15 

样例输出 #1

33