#joi2021yo2b. [joi2021_yo2_b]パンケーキ (Pancake)
[joi2021_yo2_b]パンケーキ (Pancake)
问题描述
太郎在一个薄煎饼店工作。
这家店最受欢迎的菜单是由N块煎饼叠放而成的煎饼塔。这家店制作的煎饼有三种口味,分别称为A,B和C。
在这里,我们将符合以下条件的煎饼塔称为“好煎饼塔”:
- 在所有A口味的煎饼和B口味的煎饼组合中,A口味的煎饼位于B口味的煎饼上方。
- 在所有A口味的煎饼和C口味的煎饼组合中,A口味的煎饼位于C口味的煎饼上方。
- 在所有B口味的煎饼和C口味的煎饼组合中,B口味的煎饼位于C口味的煎饼上方。
例如,煎饼的口味依次为"AABBBC","ACC","BBBB"的煎饼塔都是好煎饼塔,但是口味依次为"AABABCC","CA"的煎饼塔都不是好煎饼塔。
负责摆盘的太郎可以对煎饼塔进行以下操作:
- 操作k (2 ≤ k ≤ N):在第k块煎饼的底部插入翻转铲子,然后将上面的煎饼翻转过来。也就是说,将前k块煎饼的顺序反转。
例如,对于口味依次为"ABCB"的煎饼塔,分别进行操作2,操作3,操作4,煎饼的排列顺序将变为"BACB","CBAB","BCBA"。
现在有Q盘煎饼塔,第i盘(1 ≤ i ≤ Q) 的煎饼塔的口味依次从上到下是。对于每一个煎饼塔,太郎想要用尽可能少的操作次数将其变成好煎饼塔。
给定Q盘煎饼塔的排列信息,请编写一个程序,计算每个煎饼塔变成好煎饼塔所需的最小操作次数。
约束条件
- 2 ≤ N ≤ 13。
- 1 ≤ Q ≤ 100,000。
- 是字符'A'、'B'、'C'中的一个(1 ≤ i ≤ Q,1 ≤ j ≤ N)。
子任务
- (4 分) N ≤ 5,Q = 1。
- (10 分) N ≤ 5。
- (60 分) Q = 1。
- (26 分) 没有额外的约束条件。
输入
输入以以下格式从标准输入中给出。
N Q S_1 S_2 ⋮ S_Q
其中,S_i (1 ≤ i ≤ Q)是长度为N的字符串,第j个字符 (1 ≤ j ≤ N)是S_{i,j}。
输出
输出Q行结果到标准输出。第i行(1 ≤ i ≤ Q)输出第i盘煎饼塔变成好煎饼塔所需的最小操作次数。
示例输入1
示例输出1
对于第1盘煎饼塔,通过执行以下3次操作可以将其变为好煎饼塔:
- 执行操作4。煎饼的口味变为"BCBAA"。
- 执行操作2。煎饼的口味变为"CBBAA"。
- 执行操作5。煎饼的口味变为"AABBC"。
不可能通过执行2次或更少的操作将其变为好煎饼塔,因此在第1行输出3。
对于第2盘煎饼塔,通过执行以下2次操作可以将其变为好煎饼塔:
- 执行操作5。煎饼的口味变为"BABCC"。
- 执行操作2。煎饼的口味变为"ABBCC"。
不可能通过执行1次或更少的操作将其变为好煎饼塔,因此在第2行输出2。
第3盘煎饼塔已经是好煎饼塔了,不需要执行任何操作。因此,在第3行输出0。
示例输入2
示例输出2
请注意,可能存在多个煎饼塔的排列方式相同的情况。