#9284. 「2025CSP-X」IOI串(ioi) 普及−

时间限制:1000 ms 内存限制:256 MiB 输入文件:ioi.in 输出文件:ioi.out
题目类型:传统 评测方式:文本比较
上传者: Wind_Rises

注意

本题采用文件输入输出。

输入文件为 ioi.in, 输出文件为ioi.out

题目描述

小明对字符串"IOI"怀有特殊的感情,他定义一种由大写英文字母'I'和'0'构成的字符串为“好串”,当且仅当它可以被划分为三个非空部分,依次为:

第一部分:连续若干个'I

第二部分:连续若干个'0'

第三部分:连续若干个'I'

如:

"IIIOOIIII"是一个好串,"IOI"也是一个好串;"OIOI","IIO”都不是好串。

现在,小明有一个长度为n的字符串S,且S仅包含字符I'和'0'

他可以进行任意次修改操作,每一次操作可将字符串中某一个位置的字符替换成另一个字符(即把'I'改为'0',或把'0'改为'I')。

例如:

当 S="IIIOOOIOOII"时,根据上述定义,S 不是一个“好串”,但小明可以有多种方法通过修改操作把S变为“好串”:

方法1:把第7个字符'I'改为'0',经过1次操作得到"III000000II";

方法2:分别把第8个和第9个字符'0'改为'',经过2次操作得到"IIIOOOIIIII"。

可以确定,至少经过1次修改操作才能把上面的字符串S变为“好串”。

你的任务:

告诉你小明的字符串S,请你帮小明计算,至少需要进行多少次修改操作,才能将字符串S变为一个“好串”。如果S已经是一个“好串”,输出

输入格式

从文件 ioi.in 中读入数据。

从文件 ioi.in 中读入数据。

一行,仅由'I'和'0'两种字符组成的字符串

输出格式

输出到文件 ioi.out 中。

输出到文件 ioi.out 中。

一行,包含一个整数,表示把字符串 修改为“好串”需要的最少的修改次数。

样例

样例输入 1

IIIOOOIOOII

样例输出 1

1

样例输入 2

IOOIOOIOOOII

样例输出 2

2

样例 3 见选手目录下的 ioi/ex ioi3.in与ioi/ex ioi3.ans.

样例 4 轮试题 见选手目录下的 ioi/ex ioi4.in与ioi/ex ioi4.ans.

数据范围与提示

【数据范围】 对于所有的数据,字符串的长度 满足 ,且字符串中仅包含大写英文字母'I'和'O'。

测试点范围 n ≤ 特殊性质
1 1000 字符全部为 'I'
2 字符全部为 'O'
3~13 200
14~20 5 × 10³