[AGC019D] Shift and Flip

题意翻译

给你两个01串A和B,你可以进行以下3种操作: 1. 将A左移一位(如"0011" -> "0110") 2. 将A右移一位(如"0011" -> "1001") 3. 选择一个满足$B_i=1$的位置i,令$A_i=1-A_i$ 问要使A和B相等至少要进行几次操作。

题目描述

[problemUrl]: https://atcoder.jp/contests/agc019/tasks/agc019_d $ 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 $ と出力してください。

输入输出格式

输入格式


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

输出格式


文字列 $ A,\ B $ を一致させるために必要な最小の操作回数を出力せよ。ただし、これが不可能である場合は $ -1 $ と出力せよ。

输入输出样例

输入样例 #1

1010
1100

输出样例 #1

3

输入样例 #2

1
0

输出样例 #2

-1

输入样例 #3

11010
10001

输出样例 #3

4

输入样例 #4

0100100
1111111

输出样例 #4

5

说明

### 制約 - $ 1\ \leq\ |A|\ =\ |B|\ \leq\ 2,000 $ - $ A,\ B $ は $ 0 $ と $ 1 $ からなる。 ### Sample Explanation 1 目標を達成する最短の操作列を一つ示します。 - $ A_1 $ を反転: $ A\ =\ 0010 $ - $ A $ を左にシフト: $ A\ =\ 0100 $ - $ A_1 $ を再度反転: $ A\ =\ 1100 $ ### Sample Explanation 2 $ A $ の唯一のビットを反転させる方法はありません。 ### Sample Explanation 3 目標を達成する最短の操作列を一つ示します。 - $ A $ を右にシフト: $ A\ =\ 01101 $ - $ A_5 $ を反転: $ A\ =\ 01100 $ - $ A $ を左にシフト: $ A\ =\ 11000 $ - $ A $ を再度左にシフト: $ A\ =\ 10001 $ ### Sample Explanation 4 $ A_1 $, $ A_3 $, $ A_4 $, $ A_6 $, $ A_7 $ を任意の順序で反転すればよいです。