← 返回题目列表

AtCoder · agc049_b

B. 翻转数字

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

分数: 600 点

问题陈述

给出的是长度-N 字符串 S 和 T 组成 0 和 1。 您可以进行以下操作 S 任意次数:

  • 选择 i (2 \leq i \leq N)这样 S_i=1,并替换 S_i 与 0。 另外,反转 S_{i-1},即改为 1 如果是 0 现在,反之亦然。

是否可以使 S 完全匹配 T? 如果可以的话,至少需要多少次手术?

约束

  • 1 \leq N \leq 5 \times 10^5
  • S 是一个长度为的字符串 N 组成 0 和 1.
  • T 是一个长度为的字符串 N 组成 0 和 1.

输入

输入由标准输入按以下格式给出:

N
S
T

输出

如果可以的话 S 完全匹配 T,打印所需的最少操作数。 否则,打印 -1.


示例输入 1

3
001
100

示例输出 1

2

我们可以这样做: 001 → (选择 i=3) → 010 → (选择 i=2) → 100.


示例输入 2

3
001
110

示例输出 2

-1

示例输入 3

5
10111
01010

示例输出 3

5