This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fi first
#define se second
#define ll long long
#define dl double long
using namespace std;
const int NN = 1e9 + 7;
const int N = 1e6 + 1;
const int M = 2;
const ll mod = 1e9 + 7;
const int inf = 1e9 + 7;
const dl rf = 1e-14;
const int B = sqrt(N);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
string s,t;
int d[N][3][2];
void upd( int &x , int y )
{
x = min( x , y );
}
void solve1()
{
cin >> n >> s >> t;
s = '#' + s;
t = '#' + t;
for( int i = 0; i <= n; i++ ){
for( int j = 0; j < 3; j++ ){
for( int h = 0; h < 2; h++ ){
d[i][j][h] = 1e9;
}
}
}
d[0][0][0] = 0;
for( int i = 1; i <= n; i++ ){
for( int j = 0; j < 3; j++ ){
for( int h = 0; h < 2; h++ ){
upd( d[i][j][h] , d[i - 1][j][h] );
upd( d[i][0][h] , d[i - 1][j][h] );
upd( d[i][j][0] , d[i - 1][j][h] );
upd( d[i][0][0] , d[i - 1][j][h] );
if( j == 0 ){
upd( d[i][1][0] , d[i - 1][j][h] + 1 );
upd( d[i][2][0] , d[i - 1][j][h] + 1 );
if( h == 0 ){
upd( d[i][1][1] , d[i - 1][j][h] + 2 );
upd( d[i][2][1] , d[i - 1][j][h] + 2 );
}
}
if( h == 0 ){
upd( d[i][j][1] , d[i - 1][j][h] + 1 );
upd( d[i][0][1] , d[i - 1][j][h] + 1 );
}
}
}
for( int j = 0; j < 3; j++ ){
for( int h = 0; h < 2; h++ ){
int a = s[i] - '0';
int b = t[i] - '0';
if( j == 1 )a = 0;
else if( j == 2 )a = 1;
if( h == 1 )a ^= 1;
if( a != b ){
d[i][j][h] = 1e9;
}
}
}
}
int res = 1e9;
for( int i = 0; i < 3; i++ ){
for( int h = 0; h < 2; h++ ){
res = min( res , d[n][i][h] );
}
}
cout << res;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
//freopen( "input.txt" , "r" , stdin );
//freopen( "output.txt" , "w" , stdout );
int cghf = 1;//cin >> cghf;
while( cghf-- ){
solve1();
}
}
# | 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... |