← 返回题目列表

AtCoder · agc019_d

D. 移位和翻转

中文机器翻译题面 查看原题

分数: 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 以任意顺序。