Expert.
Put your skills to the test.

Problem summary

Add two binary strings whose question marks independently stand for either bit. For each output position print its bit if every completion agrees, otherwise ?. Include an uncertain leading position if some sums need it.

Constraints

Each string has 1 to 60 characters.

Worked example

Official sample; other valid outputs may exist.

101??001
1?01101

??????110

Solution analysis

1. Process columns from least to most significant. Maintain the set of possible incoming carry bits, initially {0}. For each allowed pair of input bits and each possible carry, collect the result bit and outgoing carry.
2. Print a definite bit when its possible set has one member and ? when both occur. Carry uncertainty must be propagated as a set, rather than treating ? as a single arithmetic value. One extra zero-padded column emits any final carry.
3. For the sample, all eight possible sums end in 110, but the remaining six positions vary, including the leading one. Consequently the result is ??????110.

Why it works

At a column, every possible carry is attainable by some completion of lower columns. Current unknown bits are independent of all lower bits, so combining all allowed bits with every attainable carry yields exactly all attainable output bits and next carries. Induction proves every output position’s set is exact. Removing only definitely zero leading positions preserves uncertain leading bits.

Watch out. The answer can start with ?. Treat the two inputs’ question marks independently.

An independently written complete program with standard headers.

// Key idea: At a column, every possible carry is attainable by some completion of lower columns.
// Current unknown bits are independent of all lower bits, so combining all allowed bits with every
// attainable carry yields exactly all attainable output bits and next carries.
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string a,b;
    cin>>a>>b;
    reverse(a.begin(),a.end());
    reverse(b.begin(),b.end());
    size_t length=max(a.size(),b.size());
    a.resize(length+1,'0');
    b.resize(length+1,'0');
    int carries=1;
    string answer;
    for(size_t i=0;i<=length;++i){
        int bits=0,nextCarries=0;
        for(int x=0;x<=1;++x){
            if(a[i]!='?'&&a[i]-'0'!=x){
                continue;
            }
            for(int y=0;y<=1;++y){
                if(b[i]!='?'&&b[i]-'0'!=y){
                    continue;
                }
                for(int carry=0;carry<=1;++carry){
                    if((carries&(1<<carry))!=0){
                        int sum=x+y+carry;
                        bits|=1<<(sum%2);
                        nextCarries|=1<<(sum/2);
                    }
                }
            }
        }
        answer+=(bits==1?'0':bits==2?'1':'?');
        carries=nextCarries;
    }
    while(answer.size()>1&&answer.back()=='0'){
        answer.pop_back();
    }
    reverse(answer.begin(),answer.end());
    cout<<answer<<'\n';
}