Score : 1400 points
You are given strings s and t, both of length N.
s and t consist of 0
and 1
. Additionally, in these strings, the same character never occurs three or more times in a row.
You can modify s by repeatedly performing the following operation:
0
with 1
, and 1
with 0
), under the condition that the same character would not occur three or more times in a row in s after the operation.Your objective is to make s equal to t. Find the minimum number of operations required.
0
and 1
.Input is given from Standard Input in the following format:
N s t
Find the minimum number of operations required to make s equal to t. It can be proved that the objective is always achievable in a finite number of operations.
4 0011 0101
4
One possible solution is 0011
→ 1011
→ 1001
→ 1101
→ 0101
.
1 0 0
0
8 00110011 10101010
10