You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC119B] Electric Board

题面翻译

给定两个长度为$\textrm N$的0/1串$\textrm S$和$\textrm T$，每次对第一个串：选一个0移动到相邻的一段1之前或之后或中间，求最少经过多少次能使两个串相同。

输入

三行，分别对应$\textrm N,S,T$；

输出

一行，最小的操作次数，若无法使两个串相同则输出$\textrm -1$.

题目描述

いま、電光掲示板に 0 と 1 から成る長さ $N$ の文字列 $S$ が表示されています。

あなたは次の操作を何回でも行うことができます。なお、ここでは電光掲示板に表示されている文字列の $i$ $(1\ \leq\ i\ \leq\ N)$ 文字目を $S_i$ と表します。

操作 整数 $(l,\ r)$ $(1\ \leq\ l\ <\ r\ \leq\ N)$ であって、次の条件のうちいずれかを満たすものを $1$ 組選び、$S_l$ と $S_r$ を入れ替える。

• $S_l=$ 0 かつ $S_{l+1}=\cdots=S_r=$ 1 を満たす。
• $S_{l}=\cdots=S_{r-1}=$ 1 かつ $S_r=$ 0 を満たす。

電光掲示板に表示されている文字列を $T$ に一致させることができるか判定し、可能な場合は操作回数として考えられる最小の値を求めてください。

输入格式

入力は以下の形式で標準入力から与えられます。

$N$ $S$ $T$

输出格式

電光掲示板に表示されている文字列を $T$ にすることが不可能な場合は、-1 を出力してください。

可能な場合は、操作回数として考えられる最小の値を出力してください。

样例 #1

样例输入 #1

7
1110110
1010111

样例输出 #1

2

样例 #2

样例输入 #2

20
11111000000000011111
11111000000000011111

样例输出 #2

0

样例 #3

样例输入 #3

6
111100
111000

样例输出 #3

-1

样例 #4

样例输入 #4

119
10101111011101001011111000111111101011110011010111111111111111010111111111111110111111110111110111101111111111110111011
11111111111111111111111111011111101011111011110111110010100101001110111011110111111111110010011111101111111101110111011

样例输出 #4

22

提示

制約

• $2\ \leq\ N\ \leq\ 500000$
• $S$ は 0 と 1 からなる長さ $N$ の文字列である
• $T$ は 0 と 1 からなる長さ $N$ の文字列である

Sample Explanation 1

例えば以下のように操作を行えば、$2$ 回の操作で電光掲示板に表示されている文字列を 1010111 にすることができます。 - $(l,\ r)\ =\ (2,\ 4)$ を選んで操作を行う。そのとき、電光掲示板の文字列は 1110110 から 1011110 に変化する。 - $(l,\ r)\ =\ (4,\ 7)$ を選んで操作を行う。そのとき、電光掲示板の文字列は 1011110 から 1010111 に変化する。

Sample Explanation 2

操作を行う前の時点で、電光掲示板に表示されている文字列が $T$ であるため、答えは $0$ となります。

Sample Explanation 3

どのように操作を行っても、電光掲示板に文字列 $T$ を表示させることが不可能な場合は、-1 と出力してください。