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

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 122
作問者 : startcppstartcpp

2 ProblemId : 344 / 出題時の順位表

問題文

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

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

入力

T
S1
…
ST

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

出力

$i$行目に$K_i$を出力してください。(先頭行は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

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

提出ページヘ