/ 
実行時間制限: 2 sec / メモリ制限: 256 MB
配点 : 1000 点
問題文
0 と 1 からなる同じ長さの二つの文字列 A = A_1 A_2 ... A_n と B = B_1 B_2 ... B_n があります。
あなたは、以下の操作を任意の順序で何度でも行って A を変化させることができます。
- A を一文字左にシフトする（すなわち、A = A_1 A_2 ... A_n として A を A_2 A_3 ... A_n A_1 に置き換える）。
- A を一文字右にシフトする（すなわち、A = A_1 A_2 ... A_n として A を A_n A_1 A_2 ... A_{n-1} に置き換える）。
- B_i = 1 であるような i をいずれか一つ選び、A_i を反転する（すなわち、A_i = 1 - A_i とする）。
あなたの目標は文字列 A, B を一致させることです。
これに必要な最小の操作回数を出力してください。ただし、これが不可能である場合は -1 と出力してください。
制約
- 1 \leq |A| = |B| \leq 2,000
- A, B は 0 と 1 からなる。
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
文字列 A, B を一致させるために必要な最小の操作回数を出力せよ。ただし、これが不可能である場合は -1 と出力せよ。
入力例 1
1010 1100
出力例 1
3
目標を達成する最短の操作列を一つ示します。
- A_1 を反転: A = 0010
- A を左にシフト: A = 0100
- A_1 を再度反転: A = 1100
入力例 2
1 0
出力例 2
-1
A の唯一のビットを反転させる方法はありません。
入力例 3
11010 10001
出力例 3
4
目標を達成する最短の操作列を一つ示します。
- A を右にシフト: A = 01101
- A_5 を反転: A = 01100
- A を左にシフト: A = 11000
- A を再度左にシフト: A = 10001
入力例 4
0100100 1111111
出力例 4
5
A_1, A_3, A_4, A_6, A_7 を任意の順序で反転すればよいです。
Score : 1000 points
Problem Statement
You have two strings A = A_1 A_2 ... A_n and B = B_1 B_2 ... B_n of the same length consisting of 0 and 1.
You can transform A using the following operations in any order and as many times as you want:
- Shift A by one character to the left (i.e., if A = A_1 A_2 ... A_n, replace A with A_2 A_3 ... A_n A_1).
- Shift A by one character to the right (i.e., if A = A_1 A_2 ... A_n, replace A with A_n A_1 A_2 ... A_{n-1}).
- Choose any i such that B_i = 1. Flip A_i (i.e., set A_i = 1 - A_i).
You goal is to make strings A and B equal.
Print the smallest number of operations required to achieve this, or -1 if the goal is unreachable.
Constraints
- 1 \leq |A| = |B| \leq 2,000
- A and B consist of 0 and 1.
Input
Input is given from Standard Input in the following format:
A B
Output
Print the smallest number of operations required to make strings A and B equal, or -1 if the goal is unreachable.
Sample Input 1
1010 1100
Sample Output 1
3
Here is one fastest way to achieve the goal:
- Flip A_1: A = 0010
- Shift A to the left: A = 0100
- Flip A_1 again: A = 1100
Sample Input 2
1 0
Sample Output 2
-1
There is no way to flip the only bit in A.
Sample Input 3
11010 10001
Sample Output 3
4
Here is one fastest way to achieve the goal:
- Shift A to the right: A = 01101
- Flip A_5: A = 01100
- Shift A to the left: A = 11000
- Shift A to the left again: A = 10001
Sample Input 4
0100100 1111111
Sample Output 4
5
Flip A_1, A_3, A_4, A_6 and A_7 in any order.