3248. 法国传统舞蹈

单点时限: 2.0 sec

内存限制: 256 MB

ECNU 的学生和老师都会跳法国传统舞蹈。

在舞会上,学生会穿着各种颜色的礼服,老师会穿着黑色的礼服,一起来跳法国传统舞蹈。所有的老师和学生在舞会一开始要按照规定的顺序(见输入解释)围成一个大圆,手拉着手,朝内。

在每一首舞曲(包括第一首)开始的时候,就要变换队形。变换队形可以有以下两种情况:

  1. 一个圆变成两个圆:一个圆从两个位置断开,然后各自结合为圆。在此过程中,除了在断开的位置有两个人的左手和两个人的右手会放开之外,其他的人的手还是紧紧地牵在一起。

  2. 两个圆变成一个圆:与 1 恰好相反。两个圆分别从两个位置断开,然后结合在一起。

注意:在变换后的队形中,所有人应该还是面朝内的。一个人也可以成一个圆,左手跟右手拉在一起就好了。(有点惨)

为了增加观赏性,规定舞会结束时,队形恰好又是一个大圆。并且大圆上的每个人的礼服颜色是预先规定的。假设大家都「足够配合」,那么演奏舞曲的乐手们至少要演奏多少支舞曲呢?

输入格式

第一行是三个整数 $N, M, K$ $(1 \leq N \leq 20, 0 \leq M \leq 5, 0 \leq K \leq 2\,000)$,分别表示参加舞会的学生数,老师数,和接下来的查询数量。

在舞会一开始,大圆一定可以表示成 1 2 3 ... N r r .. r(后面共有 $M$ 个 r)。意思是说穿着礼服颜色为 1 的学生的右手边是颜色为 2 的学生,颜色为 2 的学生右手边是颜色为 3 的学生,以此类推,颜色为 N 的学生右边是一个老师。由于老师都穿着黑色礼服,所以都是 r,不作区分。最后一个 r 右手边是颜色为 1 的学生,围成一个圆。

接下来 $K$ 行,表示的是舞会结束时规定的大圆的队形。每行恰好是 $N+M$ 个整数或字母。队形的表示方法上面是相同的。由于跳舞的时候圆会旋转,所以圆从哪个人开始数其实是不影响的。

输入保证有解。

输出格式

对于每次查询,输出最少需要多少支舞曲。

样例

Input
5 0 1
1 2 4 3 5
Output
2
Input
7 5 2
6 7 r r r r r 1 2 3 4 5
6 7 r 1 2 3 4 r r r r 5
Output
0
2

提示

样例 1:第一支舞曲开始时,3 和 4 之间,4 和 5 之间断开,变成 5 1 2 3 和 4(一个人)两个圆;第二支舞曲开始时,2 和 3 分开,4 的左右手分开,合并形成大圆,就能达到要求。

10 人解决,14 人已尝试。

14 份提交通过,共有 32 份提交。

5.8 EMB 奖励。

创建: 7 年,5 月前.

修改: 7 年,1 月前.

最后提交: 3 年,10 月前.

来源: 2017 华东师范大学网赛

题目标签