Untitled

mail@pastecode.io avatar
unknown
plain_text
2 months ago
1.9 kB
39
Indexable
Never
#pragma GCC optimize("O2,no-stack-protector,unroll-loops")
#define ll long long
#define pb push_back
#define ipar(arr, n) vector<ll> arr(n); for(int i=0;i<n;i++) cin>>arr[i];
#include <cmath>
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(s) s.begin(),s.end()

using namespace std;

ll move(ll n,ll i, ll j,vector<vector<ll>>&grid,string path,ll &ocount,string &res,ll &mincount){
    if(i>=2 || j>=n) return INT_MAX;
    path+=to_string(grid[i][j]);
    if(i==1 && j==n-1) {
        if(ocount<mincount) {
            res=path;
            mincount=ocount;
        }
        else if(ocount==mincount && res!=""){
            if(path<res) res=path;
        }
        return ocount;
    }
    ll r=INT_MAX, d=INT_MAX;

    if(grid[i][j]==1) ocount++;
     d=move(n,i+1,j,grid,path,ocount,res,mincount);
     r=move(n,i,j+1,grid,path,ocount,res,mincount);
      if(grid[i][j]==1) ocount--;
    return min(r,d);
}

void allp(ll n,ll i, ll j,vector<vector<ll>>&grid,string path,ll &ocount, ll &nop,string &res2){
    if(i>=2 || j>=n) return;

    path+=to_string(grid[i][j]);
    if(i==1 && j==n-1) {
        if(path==res2) nop++;


    }

    allp(n,i+1,j,grid,path,ocount,nop,res2);
    allp(n,i,j+1,grid,path,ocount,nop,res2);
}


void in(){
    ll n;cin>>n;
    string r1,r2;
    cin>>r1>>r2;
    vector<vector<ll>>grid(2,vector<ll>(n)); //0 indexed
    for (ll i=0;i<n;i++){
        grid[0][i]=r1[i]-'0';
        grid[1][i]=r2[i]-'0';
    }
    string res="",path="";
    ll ocount=grid[0][0]==1?1:0;
    ll mincount=INT_MAX;
    ll nasc=move(n,0,0,grid,path,ocount,res,mincount);
    ll nop=0;
    string res2=res;
    allp(n,0,0,grid,"",ocount,nop,res2);

    cout<<res<<"\n";
     cout<<nop<<"\n";
}





signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    ll t;
	cin>>t;
	while(t--) in();
}
Leave a Comment