No.291 黒い文字列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : kzyKTkzyKT
3 ProblemId : 622 / 出題時の順位表

問題文

黒いものが好きなので、文字列から部分列$(Subsequence)$の"$KUROI$"をたくさん作ることにした。
一度部分列として使った文字は、別の部分列の文字として使わないようにした。

張り切って何個作れるか数えようとすると、いくつかの文字が消えていることがわかった。
消えている箇所はできるだけ部分列"$KUROI$"の数が多くなるように文字を書いた。

最大で何個の部分列"$KUROI$"が作れるか求めよ。

※遅い言語だと通らないかもしれません

入力

$S$

$1$行に文字列が与えられる。

$1 \le |S| \le 100$
$S$ : アルファベットの大文字'$A$'~'$Z$'または'$?$'で構成される文字列
'$?$'はそこの文字が消えていることを表す。

出力

文字列から作れる部分列"$KUROI$"の最大の個数を出力せよ。

サンプル

サンプル1
入力
KKUROI
出力
1

サンプル2
入力
KOIRU
出力
0

サンプル3
入力
KUROIME?UR?CHA?
出力
2

サンプル4
入力
KKUURROOII
出力
2

追加

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。