問題一覧 > 通常問題

No.1183 コイン遊び

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 281
作問者 : aspiaspi / テスター : AndrewKAndrewK
2 ProblemId : 4872 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-08-22 11:00:44

問題文

N 枚のコインが一列に並んだコイン列 a,b があります。
a,b の状態は数列 A,B によって与えられます。
A,B0,1 からなる長さ N の数列で、i 番目の数が 1 のとき i 枚目のコインが表であることを、0 のとき i 枚目のコインが裏であることを表します。
ここからあなたは任意の i,j (1ijN)を選び、 ai 枚目から j 枚目までの ji+1 枚のコインをひっくり返す(それぞれのコインに対して表を裏に、裏を表にする)操作を何回か行うことで、a の状態を b の状態にしたいと思います。
あなたが最小で何回操作する必要があるか求めてください。

入力

N
A1A2...AN
B1B2...BN

数列 A,B は空白区切りで与えられます。
1N106
Ai および Bi0 または 1
入力は全て整数

出力

コインを数列 B の状態にするために必要な最小の操作の数を一行で出力し、最後に改行してください。

サンプル

サンプル1
入力
4
0 0 0 1
1 1 0 1
出力
1

1 枚目から 2 枚目までのコインを裏返すことで、コインの状態を (1,1,0,1) にすることができます。

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

1 回目の操作で 1 枚目から 3 枚目までのコインを裏返すことで、コインの状態は (1,1,0,1,0,0,0) となります。
2 回目の操作で 5 枚目のコインを裏返すことで、コインの状態は (1,1,0,1,1,0,0) となります。
3 回目の操作で 7 枚目のコインを裏返すことで、コインの状態は (1,1,0,1,1,0,1) となります。

サンプル3
入力
20
0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 0 0 0 0 0
1 0 1 1 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1
出力
5

5 回の操作でコインを A の状態から B の状態にすることが出来ます。

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