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>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # pragma GCC optimize "-O3"
// # define int long long
using namespace std;
const int N = 1e6 + 7;
const int mod = 1e9 + 7;
vector < vector < int > > vc = { {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 1}, {2, 3}, {3, 1}, {3, 2}};
//{1, 2, 3}, { 1, 3, 2 }, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1} };
// map < int, map < vector < int >, int > > dp;
int n, cnt[20][20], dp[N][10], change[2][10];
string a, b;
int get( int i, int x ) {
if ( (int)vc[x].size() == 0 ) {
int mn = N;
for ( int j = 0; j < 10; j++ ) {
mn = min( mn, dp[i - 1][j] );
}
return mn + (a[i] != b[i]);
}
int mn = N;
for ( int y = 0; y < 10; y++ ) {
int vsz = vc[x].size(), usz = vc[y].size();
if ( vsz <= usz ) {
mn = min( mn, dp[i - 1][y] + vsz - cnt[x][y] );
}
else {
mn = min( mn, dp[i - 1][y] + vsz - cnt[y][x] );
}
}
return mn;
}
int32_t main() {
speed;
cin >> n;
cin >> a >> b;
for ( int i = 0; i < 10; i++ ) {
for ( int j = 0; j < 10; j++ ) {
int vsz = vc[i].size(), mx = 0;
for ( int mask = 0; mask < (1 << vsz); mask++ ) {
vector < int > x;
int cnt = 0;
for ( int bit = 0; bit < 3; bit++ ) {
if ( (mask >> bit) & 1 ) {
x.push_back( vc[i][bit] );
cnt++;
}
}
int ok = 0;
if ( cnt ) {
int ind = 0;
for ( auto z: vc[j] ) {
if ( ind < cnt && z == x[ind] ) {
ind++;
}
}
if ( ind == cnt ) {
ok = 1;
}
}
if ( ok ) {
mx = max( mx, cnt );
}
}
cnt[i][j] = mx;
}
}
for ( int i = 0; i < 10; i++ ) {
char x = '0', y = '1';
for ( auto j: vc[i] ) {
if ( j == 1 ) {
x = '0';
y = '0';
}
else if ( j == 2 ) {
x = '1';
y = '1';
}
else {
if ( y == '0' ) {
y = '1';
}
else {
y = '0';
}
if ( x == '0' ) {
x = '1';
}
else {
x = '0';
}
}
}
change[0][i] = x - '0';
change[1][i] = y - '0';
}
for ( int j = 0; j < 10; j++ ) {
if ( ('0' + change[a[0] - '0'][j]) != b[0] ) {
dp[0][j] = N;
continue;
}
dp[0][j] = vc[j].size();
}
if ( a[0] != b[0] ) {
dp[0][0] = 1;
}
for ( int i = 1; i < n; i++ ) {
for ( int ind = 0; ind < 10; ind++ ) {
if ( ('0' + change[a[i] - '0'][ind]) != b[i] ) {
dp[i][ind] = N;
continue;
}
dp[i][ind] = get( i, ind );
/*for ( auto j: v ) {
cout << j << ' ';
}
cout << '\n';
cout << i << ' ' << dp[i][v] << '\n';
cout << "------------\n";*/
}
}
int mn = N;
for ( int i = 0; i < 10; i++ ) {
mn = min( mn, dp[n - 1][i] );
}
cout << mn << '\n';
}
/*
8
11011100
01101001
13
1010010010100
0000111001011
18
001100010010000110
110110001000100101
*/
# | 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... |