제출 #2646

#제출 시각아이디문제언어결과실행 시간메모리
2646tncks0121계산식 복원 (GCJ12KOR_formula)C++98
40 / 40
148 ms1704 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...