問題一覧 > 通常問題

No.150 "良問"(良問とは言っていない

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 240
作問者 : startcpp
4 ProblemId : 344 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2015-11-14 17:48:07

問題文

ある文字列がT個与えられる。i+1(1≤i≤T)行目には文字列Siが与えられる
文字列Siの先頭から検索していったとき、 goodという部分文字列が見つかり、かつ、それ以降にproblemという部分文字列が見つかったとき、文字列Siは良問であるという。
全く見つからなかった場合は、文字列Siは良問ではない。

あなたは文字列Siの内の任意の場所の1文字を’a’～’z’のいずれかに書き換えるという操作を繰り返し行う。
文字列Siを良問にするまでに必要な操作の回数の最小値をKiとする。Kiをi行目に出力せよ。

入力

T
S1
…
ST

1≤T≤100
11≤Sの長さ≤100
S内の全ての文字は’a’ ～ ‘z’のいずれかになっている。

出力

i行目にKiを出力してください。(先頭行は1行目とします。)
最後に改行してください。

サンプル

サンプル1
入力
3
veryverygoodproblem
goodexcellentproblems
problemgood
出力
0
0
10

この入力例において
S1 = "veryverygoodproblem"
S2 = "goodexcellentproblems"
S3 = "problemgood"
である。このとき、
S1は最初から良問
S2も最初から良問
S3は3文字目('o')以外の文字を修正して、S3="goodproblem"とすれば良問
になる。したがって、K1 = 0、K2 = 0、K3 = 10となる。

サンプル2
入力
2
goodproblem
agdddekproblemsdl
出力
0
2

操作回数が最小となる最終的な文字列(良問)には、以下のようなものがある。
S1 = "goodproblem"
S2 = "agoodekproblemsdl
ただし、同じ操作回数でできる最終的な文字列(良問)は、複数存在することがあるので注意。

サンプル3
入力
9
geodaaaproblem
goodproblen
badendlessprobrem
podpdpprrobleem
problemgoodprobremgood
smallproblem
proproprefurohobbyhobby
gooeproblemd
itisproblemcoolgoodproblem
出力
1
1
4
5
1
4
8
1
0

サンプル4
入力
5
problemgoodproblem
problemproblem
goodgoodgood
xxxxxxxxxxxxx
badendlessproblemactivetogood
出力
0
3
6
11
3

配信終了後、追加したテストケースです。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。