No.2209 Flip and Reverse
レベル :
/ AI推定難易度 : 1250
/ 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 172
作問者 :
Shirotsume
/ テスター :
👑
AngrySadEight
ygussany
タグ : / 解いたユーザー数 172
作問者 :
問題文最終更新日: 2023-02-04 12:24:25
English (AI translation)
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
0to1, or1to0. 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
0to1, and reverse $S$. After the operation, $S =$110. - Perform the operation with $i = 1$. Change the $1$-st character of $S$ from
1to0, 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
0to1, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。