問題一覧 > 通常問題

No.2209 Flip and Reverse

レベル : / AI推定難易度 : 1250 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 172
作問者 : Shirotsume / テスター : 👑 AngrySadEight ygussany
お気に入りにしたユーザー ProblemId : 8979 / 自分の提出
問題文最終更新日: 2023-02-04 12:24:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 376 (順位表) の他の問題:

Problem Statement

You are given strings $S, T$ of length $N$ consisting of 0, 1. Find the minimum number of times the following operation must be performed on $S$ to make it equal to $T$.

  • Choose an integer $i$ satisfying $1 \leq i \leq N$. Change the $i$-th character of $S$ to the other character. That is, change 0 to 1, or 1 to 0. Then, reverse $S$.

Constraints

  • $N$ is an integer
  • $1 \leq N \leq 10^6$
  • $S,T$ are strings of length $N$ consisting of 0, 1

Input

The input is given from standard input in the following format.

$N$
$S$
$T$

Output

Output the answer.

Sample

Sample 1
Input
3
001
010
Output
2

An example of the operations is shown below.

  • Perform the operation with $i = 2$. Change the $2$-nd character of $S$ from 0 to 1, and reverse $S$. After the operation, $S =$ 110.
  • Perform the operation with $i = 1$. Change the $1$-st character of $S$ from 1 to 0, and reverse $S$. After the operation, $S =$ 010.

It is impossible to make $S$ and $T$ equal with fewer than $2$ operations.

Sample 2
Input
2
01
11
Output
1

An example of the operations is shown below.

  • Perform the operation with $i = 1$. Change the $1$-st character of $S$ from 0 to 1, and reverse $S$. After the operation, $S =$ 11.
Sample 3
Input
4
1111
1111
Output
0
Sample 4
Input
10
0110111010
1001010011
Output
5

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