← 返回题目列表

AtCoder · joi2021_yo2_b

B. 煎饼

中文机器翻译题面 查看原题

配点: 100 点

問題文

Bitaro 在一家煎饼店工作。

这家餐厅最受欢迎的菜单是 N 这是一个煎饼塔,煎饼一层一层地叠在一起。店里做的煎饼 3 口味不同,各有各的滋味。 我们称之为 A,B,C 。

在这里,我们将创建一个煎饼塔,其煎饼的排列满足以下条件。好煎饼塔。

  • 所有口味 A 煎饼和口味 B 煎饼群里,味道 A 的煎饼很好吃 它位于 B 煎饼上方。
  • 所有口味 A 煎饼和口味 C 煎饼群里,味道 A 的煎饼很好吃 它位于 C 煎饼上方。
  • 所有口味 B 煎饼和口味 C 煎饼群里,味道 B 的煎饼很好吃 它位于 C 煎饼上方。

例如,每种煎饼口味都是从上到下排序的。 所有带有 AABBBC,ACC,BBBB 的煎饼塔都是好的煎饼塔, 任何带有AABABCC,CA 的煎饼塔都不是一个好的煎饼塔。

负责煎饼的Bitaro可以在煎饼塔上执行以下操作。

  • 操作 k (2 \leqq k \leqq N):从顶部 k 将抹刀插入第二个煎饼的底部,然后从那里翻转顶部的煎饼。也就是说,从上面 k 颠倒煎饼的排列。

比如煎饼的味道是从上面开始的。 在标记为 ABCB 的煎饼塔上进行操作 如果 2,操作 3,操作 4 完成,煎饼的排列将是 BACB,CBAB,BCBA 变为。

今,Q 盘子上有一个煎饼塔,i 皿目 (1 \leqq i \leqq Q)的煎饼塔从顶部开始就有煎饼口味。 S_{i,1}S_{i,2} \cdots S_{i,N} 。 Bitaro 想要制作一个好的煎饼塔,每个煎饼塔的操作次数尽可能少。

Q 给定煎饼塔如何在盘子上排列的信息,编写一个程序来找出为每个煎饼塔制作一个好的煎饼塔所需的最少操作次数。 是

制約

  • 2 \leqq N \leqq 13.
  • 1 \leqq Q \leqq 100\,000.
  • S_{i,j} 为 A,B,C (1 \leqq i \leqq Q,1 \leqq j \leqq N).

小課題

  1. (4 点) N \leqq 5,Q = 1.
  2. (10 点) N \leqq 5.
  3. (60 点) Q = 1.
  4. (26 点)没有额外的限制。

入力

输入是按以下格式从标准输入给出的。

N Q
S_1
S_2
\vdots
S_Q

但是,S_i (1 \leqq i \leqq Q) 是长度 字符串 N 。 j 文字目 (1 \leqq j \leqq N) 是 S_{i,j} 。

出力

到标准输出 输出 Q 行。i 行目 (1 \leqq i \leqq Q)有i 对于第三个煎饼塔,输出制作一个好的煎饼塔所需的最少操作次数。


入力例 1

5 3
ABCBA
CCBAB
AAAAA

出力例 1

3
2
0

1 如果盘子上有煎饼塔,则如下 通过执行 3 操作可以制作一个好的煎饼塔。 执行

  1. 操作 4 。煎饼从上到下的味道 少于 BCBAA 变为。
  2. 操作 2 。煎饼从上到下的味道 少于 CBBAA 变为。
  3. 操作 5 。煎饼从上到下的味道 少于 AABBC 变为。

2 的操作是不可能做出一个好的煎饼塔的,所以 上线1 在行中 3 。

2 如果盘子上有煎饼塔,则如下 通过执行 2 操作可以制作一个好的煎饼塔。 执行

  1. 操作 5 。煎饼从上到下的味道 少于 BABCC 变为。
  2. 操作 2 。煎饼从上到下的味道 少于 ABBCC 变为。

1 的操作是不可能做出一个好的煎饼塔的,所以 上线2 在行中 2 。

3 对于第三块板上的煎饼塔来说,不需要执行任何操作,因为它已经是一个好的煎饼塔了。因此,3 在行中 0 。


入力例 2

2 5
AC
AC
AC
AC
AC

出力例 2

0
0
0
0
0

请注意,可能有多个煎饼塔,其中煎饼的排列方式相同。


入力例 3

13 1
ABCCABCBACBAA

出力例 3

9

入力例 4

13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA

出力例 4

4
6
2
10