#include <bits/stdc++.h>
#define TASK "kasdjkasdj"
#define INT_LIM (int) 2147483647
#define LL_LIM (long long) 9223372036854775807
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define ll long long
#define pii pair<int,int>
using namespace std;
///------------------------------------------///
void minimize(int &x, const int &y)
{
if (x>y) x = y;
}
int n;
int a[1000005];
int b[1000005];
void inp()
{
cin >> n;
FOR(i, 1, n)
{
char x;
cin >> x;
if (x=='1') a[i] = 1;
}
FOR(i, 1, n)
{
char x;
cin >> x;
if (x=='1') b[i] = 1;
}
}
int f[1000005][3];
void solve()
{
f[1][2] = (a[1]!=b[1]);
f[1][1] = (b[1]!=1)+1;
f[1][0] = (b[1]!=0)+1;
FOR(i, 2, n) FOR(s1, 0, 2)
{
f[i][s1] = INT_LIM;
FOR(s2, 0, 2)
{
int t1 = a[i], t2 = a[i-1];
if (s1<2) t1 = s1;
if (s2<2) t2 = s2;
t1 = (t1!=b[i]);
t2 = (t2!=b[i-1]);
int g = 0;
if (t1==1 && t2==0) g = 1;
if (s1==s2)
{
minimize(f[i][s1], f[i-1][s2]+g);
continue;
}
if (s1<2) minimize(f[i][s1], f[i-1][s2]+1+g);
else minimize(f[i][s1], f[i-1][s2]+g);
}
// cout << i << ' ' << s1 << ' ' << f[i][s1] << endl;
}
int ans = INT_LIM;
minimize(ans, f[n][0]);
minimize(ans, f[n][1]);
minimize(ans, f[n][2]);
cout << ans;
}
signed main()
{
///--------------------------///
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
if (fopen(TASK".INP","r")!=NULL)
{
freopen(TASK".INP","r",stdin);
freopen(TASK".OUT","w",stdout);
}
///--------------------------///
int NTEST = 1;
//cin >> NTEST;
while (NTEST--)
{
inp();
solve();
}
return 0;
}
///------------------------------------------///
Compilation message (stderr)
lamp.cpp: In function 'int main()':
lamp.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
87 | freopen(TASK".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
88 | freopen(TASK".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |