This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
//####################
//Lamps
//####################
#include<bits/stdc++.h>
using namespace std;
string A,B;
const int inf = 2*1e6;
bool apply(bool a,int m){
if(m==1)return 0;
if(m==2)return 1;
if(m==3)return !a;
return a;
}
int dp[(int)1e6][4][4][4];
int solve(int pos, int s1=0,int s2=0,int s3=0){
if(pos==A.size())return 0;
if(dp[pos][s1][s2][s3]!=-1)return dp[pos][s1][s2][s3];
vector<int> st = {s1,s2,s3};
int re = inf;
for(int a=0;a<4;a++)
for(int b=0;b<4;b++)
for(int c=0;c<4;c++){
//les cas impossibles
if(a==0 && (b || c))continue;
if(b==0 && c)continue;
if((a==b && a!=0) || (b==c && b!=0) || (a==c && a!=0))continue;
int cost = (bool)a+(bool)b+bool(c);
if(a==s1){
cost-=(bool)a;
if(b==s2){
cost-=(bool)b;
if(c==s3)
cost-=(bool)c;
}
}
bool r = (A[pos]-'0');
r = apply(r,a);
r = apply(r,b);
r = apply(r,c);
if(r==(bool)(B[pos]-'0')){
re = min(re, cost+solve(pos+1,a,b,c));
}
}
return dp[pos][s1][s2][s3]=re;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie();
int n; cin >> n;
cin >> A >> B;
for(int i = 0;i<1e6;i++){
for(int a=0;a<4;a++)
for(int b=0;b<4;b++)
for(int c=0;c<4;c++)
dp[i][a][b][c] = -1;
}
cout<<solve(0,0,0,0)<<endl;
return 0;
};
Compilation message (stderr)
lamp.cpp: In function 'int solve(int, int, int, int)':
lamp.cpp:18:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
18 | if(pos==A.size())return 0;
| ~~~^~~~~~~~~~
# | 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... |