文字の種類が 0 と 1 のみからなる文字列 S が与えられます。以下の操作を繰り返すことで、S を T に変えたいです。
クエリが Q 回与えられます。i 番目のクエリで 1 を少なくとも一つ含む文字列 S_i, T_i が与えられるので、S_i を T_i に変えるために必要な操作回数の最小値を、それぞれのクエリについて求めてください。
Q S_1 T_1 ... S_Q T_Q
1 行目では、クエリの個数 Q が与えられる。
2 行目以降 Q 行は、クエリが与えられる。 i+1 行目では S_i と T_i が空白区切りで与えられる。
0
と 1
のみからなる文字列である。1
を少なくとも 1 つ含む文字列である。出力は Q 行からなる。
i 行目には、i 番目のクエリに対する結果を出力せよ。
4 101 110 101 101 1010 1101 11011001 10010101
1 0 3 12
101
を T = 110
と一致させるために必要な操作回数の最小値を求める必要があります。以下の画像のように、 S の中に登場する 1
の中で最も右にあるものが含まれるようにスリットを置き、スリット中の文字列を書き換えることで 1 回の操作で S と T を一致させることができます。