/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
0と1からなる長さ N の文字列 S,T が与えられます。 S の i 文字目を S_i と表します。
あおばさんは文字列 S に対して以下の 2 種類の操作を行うことで、 S を T に一致させたいです。
-
操作 1：S_iS_{i+1}S_{i+2} が
001,100どちらかに等しいような i (1 \leq i \leq N-2) を選ぶ。
そして、その 3 文字を001,100どちらかに置き換える。 -
操作 2：S_iS_{i+1}S_{i+2} が
110,011どちらかに等しいような i (1 \leq i \leq N-2) を選ぶ。
そして、その 3 文字を110,011どちらかに置き換える。
あおばさんは操作 2 は好きですが、操作 1 は嫌いです。S を T に一致させるために操作 1 を最小何回行えば良いですか。
何回操作を行っても一致させることができない場合は -1 を出力してください。
制約
- 3 \leq N \leq 3 \times 10 ^ 5
- N は整数である
- S,T は
0,1からなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N S T
出力
S を T に一致させるために必要な 操作 1 の回数の最小値を整数で出力せよ。
一致させることが不可能な場合は -1 と出力せよ。
入力例 1
7 1011110 1100111
出力例 1
1
まず、i=5 として操作 2 を行い、S= 1011011 にします。
次に、i=3 として操作 2 を行い、S= 1001111 にします。
最後に、i=2 として操作 1 を行い、S= 1100111 にします。
これにより S を T と一致させることができました。操作 1 を最低 1 回行う必要があるので答えは 1 です。
入力例 2
3 110 101
出力例 2
-1
S と T を一致させることはできません。
入力例 3
26 10101000010101010101010111 01110101000111001011010100
出力例 3
24