No.1183 Coin Game
Problem Statement
There are coin rows $a,b$, each consisting of $N$ coins arranged in a row.
The states of $a,b$ are given by sequences $A,B$.
$A,B$ are sequences of length $N$ consisting of $0, 1$. When the $i$-th number is $1$, the $i$-th coin is heads, and when it is $0$, the $i$-th coin is tails.
From here, you want to turn the state of $a$ into the state of $b$ by performing some number of times the operation of choosing any $i,j$ ($1\leqq i\leqq j \leqq N$) and flipping the $j-i+1$ coins from the $i$-th through the $j$-th coin of $a$ (changing heads to tails and tails to heads for each coin).
Find the minimum number of operations you need to perform.
Input
$N$ $A_1\;\,A_2\;\,...\;\,A_N$ $B_1\;\,B_2\;\,...\;\,B_N$
The sequences $A, B$ are given separated by spaces.
$1\leqq N\leqq 10^6$
$A_i$ and $B_i$ are $0$ or $1$
All inputs are integers
Output
Output on one line the minimum number of operations required to bring the coins to the state of sequence $B$, followed by a newline at the end.
Sample
Sample 1
Input
4 0 0 0 1 1 1 0 1
Output
1
By flipping the coins from the $1$-st through the $2$-nd, the state of the coins can be made $(1, 1, 0, 1)$.
Sample 2
Input
7 0 0 1 1 0 0 0 1 1 0 1 1 0 1
Output
3
By flipping the coins from the $1$-st through the $3$-rd in the $1$-st operation, the state of the coins becomes $(1, 1, 0, 1, 0, 0, 0)$.
By flipping the $5$-th coin in the $2$-nd operation, the state of the coins becomes $(1, 1, 0, 1, 1, 0, 0)$.
By flipping the $7$-th coin in the $3$-rd operation, the state of the coins becomes $(1, 1, 0, 1, 1, 0, 1)$.
Sample 3
Input
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
Output
5
With $5$ operations, the coins can be changed from the state $A$ to the state $B$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
aspi
AndrewK