Submission #2646

#	Time	Username	Problem	Language	Result	Execution time	Memory
2646		tncks0121	계산식 복원 (GCJ12KOR_formula)	C++98	40 / 40	148 ms	1704 KiB

B

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <assert.h>
#include <memory.h>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long llu;
typedef double lf;
typedef long double llf;

const int N_ = 500;

int TC, TCC;

char A[N_], B[N_], C[N_];
int AN, BN, CN;
char op;

inline int calc (int a, int b) {
    return (op == '+') ? (a+b) : (a-b);
}

struct F {
    string a, b, c;
    F(string a = "", string b = "", string c = ""): a(a), b(b), c(c) { }
    bool operator< (const F &s) const {
        if(a != s.a) return a < s.a;
        if(b != s.b) return b < s.b;
        return c < s.c;
    }
};

F Table[N_][2];
char state[N_][2];
int T;

F solve (int x, bool carry) {
    char a, b, c;


    if(AN-x < 1 && BN-x < 1 && CN-x < 1) { state[x][carry] = carry ? -1 : 1; return F(); }
    if(state[x][carry]) return Table[x][carry];

   // printf("%d %d / %d %d %d\n", x, carry, AN-x, BN-x, CN-x);
    F &ret = Table[x][carry];
    bool chk = false;

    //printf("%c %c %c\n", A[AN-x], B[BN-x], C[CN-x]);
    for(a = 0; a <= 9; a++) if(AN-x < 0 || A[AN-x] == '?' || A[AN-x] == a+'0') {
        if(AN-x < 0 && a != 0) continue;
        if(a == 0 && AN-x == 1 && AN > 1) continue;
        for(b = 0; b <= 9; b++) if(BN-x < 0 || B[BN-x] == '?' || B[BN-x] == b+'0') {
            if(BN-x < 0 && b != 0) continue;
            if(b == 0 && BN-x == 1 && BN > 1) continue;
            c = calc(a, b) + calc(0, carry); if(CN-x < 0 || C[CN-x] == '?' || C[CN-x] == (c+10)%10+'0') {
                if(CN-x < 0 && (c+10)%10 != 0) continue;
                if((c+10)%10 == 0 && CN-x == 1 && CN > 1) continue;
                //printf("%d %d - %d(%c) %d(%c) %d(%c)\n", x, carry, a, A[AN-x], b, B[BN-x], c, C[CN-x]);
                F tmp = solve(x+1, (c<0 || c>9));
                if(state[x+1][c<0 || c>9] == -1) continue;
                if(AN-x > 0) tmp.a += (char)(a + '0');
                if(BN-x > 0) tmp.b += (char)(b + '0');
                if(CN-x > 0) tmp.c += (char)((c+10)%10 + '0');
                if(!chk || tmp < ret) ret = tmp, chk = true;
            }
        }
    }


    state[x][carry] = 1;
    if(ret.a.empty() && ret.b.empty() && ret.c.empty()) state[x][carry] = -1;
    //printf("%d %d : %s %c %s = %s : %d\n", x, carry, ret.a.c_str(), op, ret.b.c_str(), ret.c.c_str(), state[x][carry]);
    return ret;
}

int main() {

    int i, j;

    scanf("%d\n", &TC);
    while(++TCC <= TC) {
        scanf("%s %c %s = %s\n", A+1, &op, B+1, C+1);
        for(i = 0; i < N_; i++) Table[i][0] = Table[i][1] = F(), state[i][0] = state[i][1] = 0;

        AN = strlen(A+1); A[0] = '0'; //for(i=1; i<=AN; i++) A[i] -= '0';
        BN = strlen(B+1); B[0] = '0'; //for(i=1; i<=BN; i++) B[i] -= '0';
        CN = strlen(C+1); C[0] = '0'; //for(i=1; i<=CN; i++) C[i] -= '0';
        //printf("%d %d %d\n", AN, BN, CN);

        F res = solve(0, false);
        printf("Case #%d: %s %c %s = %s\n", TCC, res.a.c_str(), op, res.b.c_str(), res.c.c_str());
    }

    return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25