問題一覧 > 通常問題

No.1209 XOR Into You

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 90
作問者 : RhoRho / テスター : simasima_71simasima_71
24 ProblemId : 4462 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-28 18:42:40

問題文

長さ N の数列 A={A1,A2,...AN} があります。ユウは以下の操作を何回でも行うことができます。

  • 整数 i (1iN2) を選ぶ。Ai+1AiAi+1Ai+2 で置き換える。ただしここではbitごとの排他的論理和を表す。
ユウの目標は、操作によって数列 A を数列 B={B1,B2,...BN} と一致させることです。
操作によって目標を達成できるかどうか判定し、達成できるならばそのときの最小の操作回数を求めてください。

入力

N
A1 A2 ... AN
B1 B2 ... BN

入力は全て整数である
3N105
0Ai,Bi<230(1iN)

出力

操作によって問題文の目標を達成できない場合、-1を一行に出力してください。 できる場合、最小の操作回数を一行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
1 2 3
1 0 3
出力
1

操作を 1 回行うことで、数列 AB と一致させることができます。

サンプル2
入力
3
1 2 3
1 4 3
出力
-1

数列 AB と一致させることはできません。

サンプル3
入力
8
1 7 3 2 0 5 0 8
1 7 3 2 0 5 0 8
出力
0

最初から AB が一致している場合もあります。

サンプル4
入力
8
0 1 2 3 4 5 6 7
0 3 0 1 0 1 0 7
出力
7

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。