分数: 1000 点
问题陈述
你有两个字符串 A = A_1 A_2 ... A_n 和 B = B_1 B_2 ... B_n 相同长度的组成 0 和 1.
你可以改造 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}).
- 选择任意 i 这样 B_i = 1。翻转 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 以任意顺序。