A - IOI列車で行こう2
Editorial
/
Time Limit: 2 sec / Memory Limit: 128 MB
問題文
E869120国ではIOI国に続き, 新たに鉄道を敷設した。
E869120国の鉄道を走る列車はいくつかの車両が連結されたものであり, 車両には I, O の 2 種類がある。
しかし, 次のような規則でつながなければならない。
- 車両はそれぞれ異なる種類の車両としか連結できない。
- 列車に運転席を設ける関係上,列車の両端の車両は種類 I でなければならない。
列車は車両の種類を表す文字を順につなげた文字列で表され, 列車の長さはその文字列の長さであるとする。
例えば, IOIOI , IOIOIOIOIOIOIOIOI などが条件を満たす。
今, 車庫には文字列 S で表されるような車両が連結された状態がある。
編成する車両は, S の部分列でなければならない。
そのとき, 最大で何両の列車が編成できるだろうか。
入力
入力は以下の形式で標準入力から与えられる。
S
- 1 行目には、車庫の状態を表す文字列 S が与えられる。
出力
出力は以下の形式で標準出力に従うこと。
- 編成できる車両の両数を 1 行で出力せよ。
- ただし, 列車が編成できない場合は 0 と出力せよ。
制約
- 1≦|S|≦50,000
小課題
小課題 1 [ 25 点 ]
- 1 ≦ | S | ≦ 100 を満たす。
小課題 2 [ 75 点 ]
- 追加の制約はない。
入力例1
IOOIIOIOIIOI
出力例1
9
- 1, 2, 4, 6, 7, 8, 9, 11, 12 両目を選べば, 列車「 IOIOIOIOI 」が作れます。
入力例2
IOIOIIOIOI
出力例2
9
- 1, 2, 3, 4, 5, 7, 8, 9, 10 両目を選べば, 列車「 IOIOIOIOI 」が作れます。
入力例3
IIOOII
出力例3
3
問題文担当者:square1001