← 返回题目列表

Codeforces · 1370/E

E. 二进制子序列旋转

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

Naman 有两个长度为 $$$n$$$ 的二进制字符串 $$$s$$$ 和 $$$t$$$(二进制字符串是仅由字符“0”和“1”组成的字符串)。他希望尽可能少地使用以下操作将 $$$s$$$ 转换为 $$$t$$$。

在一次操作中,他可以选择 $$$s$$$ 的任意子序列并将其顺时针旋转一次。

例如,如果$$$s = 1\textbf{1}101\textbf{00}$$$,他可以选择索引(基于$$$1$$$的)$$$\{2, 6, 7 \}$$$对应的子序列并顺时针旋转它们。结果字符串将为 $$$s = 1\textbf{0}101\textbf{10}$$$。

如果通过删除一些字符而不改变剩余字符的顺序可以从 $$$b$$$ 获得 $$$a$$$,则字符串 $$$a$$$ 被称为字符串 $$$b$$$ 的子序列。

对大小为 $$$k$$$ 的序列 $$$c$$$ 执行顺时针旋转,就是执行同时设置 $$$c_1:=c_k, c_2:=c_1, c_3:=c_2, \ldots, c_k:=c_{k-1}$$$ 的操作。

确定 Naman 将 $$$s$$$ 转换为 $$$t$$$ 所需执行的最少操作数,或者说这是不可能的。

输入

第一行包含一个整数 $$$n$$$ $$$(1 \le n \le 10^6)$$$ — 字符串的长度。

第二行包含长度为 $$$n$$$ 的二进制字符串 $$$s$$$。

第三行包含长度为$$$n$$$的二进制字符串$$$t$$$。

输出

如果在任意次数的操作之后都无法将 $$$s$$$ 转换为 $$$t$$$,则打印 $$$-1$$$。

否则,打印所需的最少操作数。

示例

输入 #1

6
010000
000001

输出 #1

1

输入 #2

10
1111100000
0000011111

输出 #2

5

输入 #3

8
10101010
01010101

输出 #3

1

输入#4

10
1111100000
1111100001

输出#4

-1

注意

在第一个测试中,Naman 可以选择索引 $$$\{2, 6\}$$$ 对应的子序列并旋转一次,将 $$$s$$$ 转换为 $$$t$$$。

在第二个测试中,他可以将所有索引对应的子序列旋转$$$5$$$次。可以证明,这是所需的最少运算次数。

在上次测试中,无法将 $$$s$$$ 转换为 $$$t$$$。