A16832. New Year String
编程题
普及-
知识点
题目描述
如果一个只包含字符 $0$、$2$、$5$ 和（或）$6$ 的字符串满足以下至少一个条件，我们称它为新年字符串（New Year string）：
- 它包含连续的子串 $2026$；
- 它不包含连续的子串 $2025$。
例如，字符串 $20252026$、$21026$、$20262026$、$000$ 都是新年字符串。而字符串 $2025$、$20256$、$20252025$、$000202500020226$ 都不是新年字符串。
现在给定一个字符串 $s$。你可以进行任意次（可以为 $0$ 次）如下操作：
- 选择 $s$ 中的一个字符，将其替换为 $0$、$2$、$5$ 或 $6$ 中的任意一个字符。
请计算，将字符串 $s$ 变为新年字符串所需的最小操作次数。
- 它包含连续的子串 $2026$；
- 它不包含连续的子串 $2025$。
例如，字符串 $20252026$、$21026$、$20262026$、$000$ 都是新年字符串。而字符串 $2025$、$20256$、$20252025$、$000202500020226$ 都不是新年字符串。
现在给定一个字符串 $s$。你可以进行任意次（可以为 $0$ 次）如下操作：
- 选择 $s$ 中的一个字符，将其替换为 $0$、$2$、$5$ 或 $6$ 中的任意一个字符。
请计算，将字符串 $s$ 变为新年字符串所需的最小操作次数。
输入格式
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。
每组测试数据包括两行：
- 第一行包含一个整数 $n$（$4 \leq n \leq 20$），表示字符串 $s$ 的长度；
- 第二行包含一个长度为 $n$ 的字符串 $s$，只包含 $0$、$2$、$5$、$6$ 这四种字符。
每组测试数据包括两行：
- 第一行包含一个整数 $n$（$4 \leq n \leq 20$），表示字符串 $s$ 的长度；
- 第二行包含一个长度为 $n$ 的字符串 $s$，只包含 $0$、$2$、$5$、$6$ 这四种字符。
输出格式
对于每个测试用例，输出一个整数，表示将字符串 $s$ 变为新年字符串所需的最小操作次数。
输入输出样例
输入 #1
7 4 0000 4 2025 4 2026 8 20252026 8 20252025 9 202520256 9 202520265
输出 #1
0 1 0 0 1 1 0
说明/提示
在样例的第二个测试中，你可以将字符串的第 2 个字符替换为 2，此时字符串变为 $2225$。
在样例的第 5 个测试中，你可以将第 4 个字符替换为 $6$，则字符串变为 $20262025$。
在样例的第 6 个测试中，你可以将第 8 个字符替换为 $6$，则字符串变为 $202520266$。
在样例的第 5 个测试中，你可以将第 4 个字符替换为 $6$，则字符串变为 $20262025$。
在样例的第 6 个测试中，你可以将第 8 个字符替换为 $6$，则字符串变为 $202520266$。