D - Shift and Flip

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 1000

問題文

01 からなる同じ長さの二つの文字列 A = A_1 A_2 ... A_nB = B_1 B_2 ... B_n があります。

あなたは、以下の操作を任意の順序で何度でも行って A を変化させることができます。

  • A を一文字左にシフトする(すなわち、A = A_1 A_2 ... A_n として AA_2 A_3 ... A_n A_1 に置き換える)。
  • A を一文字右にシフトする(すなわち、A = A_1 A_2 ... A_n として AA_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, B01 からなる。

入力

入力は以下の形式で標準入力から与えられる。

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.