Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
0
と 1
からなる長さ N の文字列 S 及び T が与えられます.
あなたは,S に以下の操作を好きな回数行うことができます.
- S_i=
1
となる i (2 \leq i \leq N) を選ぶ. そして,S_i を0
で置き換える. さらに,S_{i-1} を今と異なる文字へ変更する.つまり,操作の直前で S_{i-1} が0
であれば1
に,1
であれば0
に変更する.
S を T に一致させることは可能でしょうか? また可能な場合は,そのために必要な最小の操作回数はいくらでしょうか?
制約
- 1 \leq N \leq 5 \times 10^5
- S は
0
,1
からなる長さ N の文字列. - T は
0
,1
からなる長さ N の文字列.
入力
入力は以下の形式で標準入力から与えられる.
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
Score : 600 points
Problem Statement
Given are length-N strings S and T consisting of 0
and 1
.
You can do the following operation on S any number of times:
- Choose i (2 \leq i \leq N) such that S_i=
1
, and replace S_i with0
. Additionally, invert S_{i-1}, that is, change it to1
if it is0
now and vice versa.
Is it possible to make S exactly match T? If it is possible, how many operations does it take at least?
Constraints
- 1 \leq N \leq 5 \times 10^5
- S is a string of length N consisting of
0
and1
. - T is a string of length N consisting of
0
and1
.
Input
Input is given from Standard Input in the following format:
N S T
Output
If it is possible to make S exactly match T, print the minimum number of operations it takes. Otherwise, print -1.
Sample Input 1
3 001 100
Sample Output 1
2
We can do as follows: 001
→ (choose i=3) → 010
→ (choose i=2) → 100
.
Sample Input 2
3 001 110
Sample Output 2
-1
Sample Input 3
5 10111 01010
Sample Output 3
5