#D0274. 乌龟对对碰

乌龟对对碰

游戏规则

33DAI 最近在看一个乌龟对对碰游戏。游戏规则如下(下面所有的“乌龟”指的都是乌龟玩具):

游戏道具

  • 有一个 3×33\times 3 的九宫格棋盘。编号如下:
~ 第一列 第二列 第三列
第一行 1 2 3
第二行 4 5 6
第三行 7 8 9
  • nn 个乌龟,编号 1n1\sim n,每个乌龟都有一个颜色,第 ii 个乌龟的颜色用一个整数 aia_i 表示,颜色有 1010 种,分别对应到数字 090\sim 9
  • 有一个幸运颜色 xx090\sim 9 中的一种)

游戏流程

第一步、初始的乌龟数量限制mm
第二步、按编号从小到大的顺序,依次在还存在的乌龟中拿乌龟,每拿一个,乌龟计数器 +1+1。每每个乌龟都放到一个空格子中,如果有多个空格子,放在编号最小的空格子中。
第三步、放的过程中,如果当前乌龟颜色是幸运颜色,那么乌龟数量限制 +1+1
第四步、放的过程中,如果已经放满了、或者乌龟计数器达到了乌龟数量限制,就开始进行结算。
第五步、结算后,如果乌龟计数器小于乌龟数量限制,那么会回到第二步,继续拿乌龟放到棋盘中。

结算规则

编号小的规则优先级更高,每个操作完成后都会再次从小到大检查所有规则,直到所有规则都不满足为止。

  1. 【全家福】如果当前棋盘上的乌龟颜色全都不一样,把棋盘上所有乌龟销毁,乌龟数量限制 +8+8
  2. 【同行】如果当前棋盘上 33 只颜色一样的乌龟在同一行,把这 33 只乌龟销毁,乌龟数量限制 +2+2
  3. 【同列】如果当前棋盘上 33 只颜色一样的乌龟在同一列,把这 33 只乌龟销毁,乌龟数量限制 +2+2
  4. 【对角线1】如果当前棋盘上 33 只颜色一样的乌龟在 1,5,91,5,9 这三个位置,把这 33 只乌龟销毁,乌龟数量限制 +2+2
  5. 【对角线2】如果当前棋盘上 33 只颜色一样的乌龟在 3,5,73,5,7 这三个位置,把这 33 只乌龟销毁,乌龟数量限制 +2+2
  6. 【碰】从 191\sim 9 依次检查棋盘上的每个位置 ii,如果有另一个位置 jj 上的乌龟颜色与 ii 一致(如果有多个位置,挑选最小的 jj),销毁这两只乌龟,乌龟数量限制 +1+1

常见的结算规则还有清盘的奖励,但本题不考虑。

题目描述

输入 n,mn,m 以及 nn 个乌龟的颜色 a1ana_1\sim a_n。请输出最终乌龟计数器会变为多少。

输入格式

第一行为整数 n,m,xn,m,x

第二行为一个长度为 nn 的字符串,第 ii 个字符为 aia_i

输出格式

输出最终乌龟计数器的大小。

27 10 3
012345678999892922167450000

23

样例解释

乌龟计数器 00、初始乌龟限制:1010、幸运颜色为 33

第一轮

012345678999892922167450000
~~~~~~~~~

拿了 99 个乌龟,乌龟计数器变为 99,乌龟限制变为 1111(触发了一次幸运颜色)

~ 第一列 第二列 第三列
第一行 0 1 2
第二行 3 4 5
第三行 6 7 8

结算时触发了第一条规则,棋盘清空,乌龟限制变为 1919(【全家福】 +8+8

第二轮

012345678999892922167450000
xxxxxxxxx~~~~~~~~~

拿了 99 个乌龟,乌龟计数器 1818,乌龟限制 1919

~ 第一列 第二列 第三列
第一行 9 9 9
第二行 8 9 2
第三行 9 2 2

【同行+2+2】 乌龟限制变为 2121,棋盘变为:

~ 第一列 第二列 第三列
第一行
第二行 8 9 2
第三行 9 2 2

【碰+1+1】 乌龟限制变为 2222,棋盘变为:

~ 第一列 第二列 第三列
第一行
第二行 8 2
第三行 2 2

【碰+1+1】 乌龟限制变为 2323,棋盘变为:

~ 第一列 第二列 第三列
第一行
第二行 8
第三行 2

第三轮

012345678999892922167450000
xxxxxxxxxxxxxxxxxx~~~~~

拿了 55 个乌龟,乌龟计数器 2323,乌龟限制 2323

~ 第一列 第二列 第三列
第一行 1 6 7
第二行 8 4 5
第三行 2

没有触发任何结算规则,游戏结束。

数据规模与约定

对于 100%100\% 的数据,1n10001 \le n \le 10001m1001 \le m \le 100aia_ixx 必然是 090\sim 9 中的一个。

题目保证最终的乌龟计数器大小必然小于等于 nn

数据是随机造的(当然这和本题做法也没有啥关系,只是提前声明一下 33DAI 非常懒,没有特殊构造)。