Stamps(判子) - joi2009-day1

出典: 第8回日本情報オリンピック 春季トレーニング合宿

時間制限: 1秒

メモリ制限: 64MB

IOI 国にある老舗判子メーカーのIOI堂は今年で創業101年となる. これを記念しIOI堂ではオーダーメードで長いメッセージを入れた判子を作るサービスを始めることにした. というのも昨年, IOI堂は手動で判子の特定の部分に文字を挿入したり, 抜き出したり, 入れ替えたりすることができる判子を開発し, より長い文字列の判子を作ることを可能としたのである.

今回作る判子は, アルファベットのIとOの2文字のみから構成されるIOI語を対象にする. また, 既存の機械で予め適当な1文字以上の長さの判子を作り, その文字列を適宜編集して注文のメッセージを作ることにする. ただし, 古くからの仕様により, この機械で作ることができるのは, Iで始まりIで終わる, どの連続した2文字も同一ではない文字列(例えばIやIOIやIOIO…OIOI)の判子である.

現在, IOI堂では人手が足りていないので作業時間をできる限り短くしたい. 機械作業は時間がかからないが, その後の3種類の編集作業, すなわち1つの文字を挿入する作業, 1つの文字を削除する作業, 1つの文字を入れ替える作業は, 各々1回あたり1秒の時間が必要である. 例えばIOIOIOIという文字列の判子を機械で作った後に, 3文字目をOに入れ替え, 5文字目と6文字目の間にOを1文字挿入しIOOOIOOIという文字列の判子を作ると2秒の時間が必要となる.

そこで, 注文のメッセージが与えられた時, 最短の作業時間と, 最短時間で作業した時に予め機械で作らなければならない判子の長さの最小値を求めるプログラムを書いてほしい.

Input.

入力ファイルstamps.inの1行目には, 1つの注文されたメッセージの長さを表す整数N(1 ≤ N ≤ 1000000)が書かれている. 2行目には注文されたメッセージを表すN文字のIまたはOからなる文字列Sが書かれている.

Output.

出力は標準出力に行うこと. 出力の1行目には最短の作業時間を書け. 2行目には最短時間で作業した時に予め機械で作らなければならない判子の長さの最小値を書け.

採点基準

採点用データのうち, 配点の40% 分についてはN ≤ 5000 を満たす.

例1

stamps.in	標準出力
8 IOOOIOOI	2 7

例2

stamps.in	標準出力
5 IOIOI	0 5

例3

stamps.in	標準出力
5 IIIII	2 5