codejam_2016_round1B_B.cpp

/* 1등 ikatanic 코드 참고 함 */
#include <iostream>
#include <string>
#include <algorithm>
#include <fstream>

using namespace std;

#define FOR(i, N) for(int i = 0; i < N; i++)
#define ll long long
#define INF 2e18

int main(){
    
    freopen("codejam/B/B-large-practice.in", "r", stdin);
    freopen("codejam/B/B-large-practice.out", "w", stdout);
    
    int T;
    cin >> T;
    FOR(t,T){
        string A, B;
        cin >> A >> B;
        
        ll ans = INF;
        string ansA, ansB;
        
        auto test = [&](string a, string b){
            ll diff = abs(stoll(a)-stoll(b));
            /*
             tuple로 만들면 미리 정의된 연산자 정의에 의해
             diff가 최소, diff가 같으면 a가 최소, a가 같으면 b가 최소인 값을 쉽게 선택할 수 있으므로
            */
            if(make_tuple(diff, a, b) < make_tuple(ans, ansA, ansB))
                ans = diff, ansA = a, ansB = b;
        };
        
        int len = (int)A.length();
        
        FOR(type, 2){
            //type이 0일 때 A < B 라고 가정
            //type이 1일 때 B > A 라고 가정
            
            FOR(i, len+1){
                string a = A, b = B;
                bool ok = true;
                FOR(j, i){
                    //i-1자리 까지 내림 수 발생하지 않음을 가정
                    if(a[j] == '?' && b[j] == '?') a[j] = b[j] = '0';
                    else if(a[j] == '?') a[j] = b[j];
                    else if(b[j] == '?') b[j] = a[j];
                    else if(a[j] != b[j]){
                        //내림 수 발생
                        ok = false;
                        break;
                    }
                    
                    if(j == len-1){
                        ok = false;
                        if(type) test(b, a);
                        else test(a, b);
                    }
                }
                
                //ok가 false이면 i자리 전에 내림수가 발생했므로 가정에 모순이다. 이 상황을 종료해야함
                if(!ok) break;
                
                FOR(db, 10) FOR(da, db)
                    if(a[i] == '?' || a[i] == '0'+da)
                    if(b[i] == '?' || b[i] == '0'+db){
                        //i번째 자리수에서 내림 수 발생
                        string na = a, nb = b;
                        na[i] = '0'+da;
                        nb[i] = '0'+db;
                        
                        for(int k = i+1 ; k< len ; k++){
                            //나머지 수 결정
                            if(na[k] == '?') na[k] = '9';
                            if(nb[k] == '?') nb[k] = '0';
                        }
                        if(type) test(nb, na);
                        else test(na,nb);
                    }
            }
            
            //A,B를 바꿔줘서 type이 1일 때 B > A 가정에 대해 위 코드를 재 사용하기 위함
            FOR(i, len) swap(A[i], B[i]);
        }
        
        cout << "Case #" << t+1<<": " << ansA << " " << ansB << endl;
    }
    return 0;
}