[厦门小学生 C++ 2024] 乌龟对对碰

乌龟对对碰是网络直播平台中流行的一种盲盒玩法。主播准备了一个盲盒序列，消费者需要按盲盒序列从前到后的顺序，先购买数包树脂乌龟盲盒。消费者在下单之后，主播会现场拆开消费者的树脂乌龟盲盒进行对对碰环节。 - **对对碰环节 1**：在该环节会把消费者的乌龟盲盒按 **照原盲盒序列的顺序** 拆开放在 $9$ 宫格当中，按照从上到下从左到右的顺序给 $9$ 宫格编号 $1$ 到 $9$，按照编号从小到大的顺序给每一个格子放一个乌龟。查看 $9$ 宫格是否满足下方的特定条件，满足条件按照赠送机制对应地进行操作。当满足下面的特定条件时，会把 $9$ 宫格中的部分乌龟拿走，算作要给消费者的乌龟。 当所有特定条件都不满足的时候，$9$ 宫格里的所有乌龟全部拿走，算作要给消费者的乌龟，对对碰环节结束。最终消费者获得 **自己购买的乌龟** 以及对对碰 **赠送的乌龟**。 然后进入到环节 $2$。 - **对对碰环节 2**：向消费者的未拆开的盲盒中，补充满足特定条件对应数量的赠送盲盒。即如果当前剩余 $x$ 个盲盒还没开，现在满足特定条件又赠送了 $y$ 个盲盒，那么现在剩余的盲盒数量增加到 $x+y$，将这 $y$ 个盲盒按顺序补在最后面，原盲盒序列的数量保证满足游戏过程中的赠送数量。然后进入到环节 $3$。 - **对对碰环节 3**：用剩余还没拆开的乌龟盲盒按照原盲盒序列的顺序去补充 $9$ 宫格，按照编号从小到大的顺序给空的格子放一个乌龟。然后再进入到环节 $1$。 | 特定条件 | 要求 | 赠送机制 | |:----------:|:------:|:----------:| | 条件 1 | 场上有两个颜色相同的乌龟 **（不一定相邻）** | 把场上成对出现的乌龟全部成对拿走，如果拿走了 $x$ 对乌龟那么就赠送 $x$ 个盲盒 | | 条件 2 | 当 **按照条件 1** 拿走乌龟之后刚好场上没有任何一只乌龟 | 赠送 $8$ 个盲盒 | | 条件 3 | 当 $9$ 宫格的各个位置 **都有乌龟** 并且每只乌龟的颜色 **各不相同** | $9$ 宫格中的所有乌龟拿走，赠送 $10$ 个盲盒（按本条件拿走所有乌龟后，不能按“条件 $2$ 清台”赠送盲盒）。 | 乌龟总共有 $10$ 种颜色（用 $0\sim 9$ 表示），现在假定有一个长度为 $n$ 的盲盒序列，序列用字符串 $S$ 表示，其中第 $i$ 个字符代表第 $i$ 个乌龟盲盒中乌龟的颜色。小 Z 看到别人买了很多乌龟也想组建自己的乌龟大军，于是小 Z 下单了 $a$ 个盲盒，即盲盒序列中的第 $1$ 个盲盒到第 $a$ 个盲盒，赠送盲盒从盲盒序列的第 $a+1$ 个盲盒依次往后赠送，现在小 Z 想知道自己最后能拿到多少只乌龟。 ## Input - 输入的第一行包含一个只包含数字 $0$ 到 $9$ 的字符串 $S$。 - 输入的第二行包含一个整数 $a$，代表购买的树脂乌龟盲盒数量。 ## Output 输出一个整数，代表小 Z 最终能够拿走多少只乌龟。 [samples] ## Background 本试题为 2024 年厦门市小学生 C++ 语言**复赛**试题，数据为洛谷自造。 **初赛**为笔试。 ## Note ### 样例解释 1 1. 盲盒序列：$\tt{012334567888999}$； 放进九宫格之前没开的盲盒：$\tt{0 1 2 3 3 4 5 6 7 8}$； 放入九宫格之后，如下表所示： | 0 | 1 | 2 | |---|---|---| | 3 | 3 | 4 | | 5 | 6 | 7 | 2. 手里没开的盲盒：$\tt{8}$； 已经拿走的盲盒：无； 满足条件 1（赠送 1 个盲盒），处理之后如下表所示： | 0 | 1 | 2 | |---|---|---| | | | 4 | | 5 | 6 | 7 | 3. 手里没开的盲盒：$\tt{8 8}$； 已经拿走的盲盒：$\tt{3 3}$； 放入九宫格之后，如下表所示： | 0 | 1 | 2 | |---|---|---| | 8 | 8 | 4 | | 5 | 6 | 7 | 4. 满足条件 1（赠送 1 个盲盒），处理之后如下表所示： | 0 | 1 | 2 | |---|---|---| | | | 4 | | 5 | 6 | 7 | 5. 手里没开的盲盒：$\tt{8}$； 已经拿走的盲盒：$\tt{3 3 8 8}$； 放入九宫格之后，如下表所示： | 0 | 1 | 2 | |---|---|---| | 8 | | 4 | | 5 | 6 | 7 | 6. 不满足所有 $3$ 个条件，游戏结束，$9$ 宫格里的盲盒全部拿走。 手里没开的盲盒：无； 已经拿走的盲盒：$\tt{3 3 8 8 0 1 2 8 4 5 6 7}$； 因此输出答案为 $12$。 ### 数据范围 **洛谷民间测试数据不满足特殊性质。** 对于所有数据，满足 $200\leq S$ 的长度 $\leq 5\times 10^5$，$10\leq a\leq 200$。 | 数据点编号 | $S$ 的长度 $\leq$ | $a\leq$ | 特殊性质 | |:------------:|:------------:|:----:|:----------:| | $1,2$ | $200$ | $20$ | 只满足特定条件 $1$ | | $3,4$ | $200$ | $20$ | 只满足特定条件 $1,2$ | | $5,6$ | $200$ | $20$ | 只满足特定条件 $1,3$ | | $7,8,9,10$ | $5\times 10^5$ | $1\times 10^5$ | 无特殊限制 |