A16832 | $New Year String$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

如果一个只包含字符 $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$ 变为新年字符串所需的最小操作次数。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的组数。 每组测试数据包括两行： - 第一行包含一个整数 $n$（$4 \leq n \leq 20$），表示字符串 $s$ 的长度； - 第二行包含一个长度为 $n$ 的字符串 $s$，只包含 $0$、$2$、$5$、$6$ 这四种字符。

对于每个测试用例，输出一个整数，表示将字符串 $s$ 变为新年字符串所需的最小操作次数。

输入 #1

输出 #1

C++ 编辑器

输入

输出