#include <cstdio>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
string a, b, c;
int cache[2][250];
char op, dat[3][250];
int len;
inline char minv(char k) {
if (k <= '9') return k;
if (k == '@') return '1';
return '0';
}
inline char maxv(char k) {
if (k <= '9') return k;
return '9';
}
int dp(int carry, int pos) {
int &ret = cache[carry][pos];
if (~ret) return ret;
int n = 0;
if (pos+1 < len) {
if (dp(0, pos+1) && dp(1, pos+1)) {
n = -1;
} else if (dp(1, pos+1)) {
n = 1;
} else if (!(dp(0, pos+1)))
return ret = 0;
}
char x, y, z;
int sx = minv(a[pos]), sy = minv(b[pos]), sz = minv(c[pos]);
int ex = maxv(a[pos]), ey = maxv(b[pos]), ez = maxv(c[pos]);
int sn = ~n ? n : 0, en = ~n ? n : 1;
for (x = sx; x <= ex; ++x)
for (y = sy; y <= ey; ++y)
for (n = sn; n <= en; ++n) {
if (op == '+') z = x + y - '0' - carry*10 + n;
else z = x - y + '0' + carry*10 - n;
if (z >= sz && z <= ez) return ret = 1;
}
return ret = 0;
}
inline void process(string& s) {
if (s[0] == '?' && s.size() > 1) s[0] = '@';
s = string(len - s.size(), '0') + s;
}
void calculate(string& s) {
for (int i=0; i<s.size(); ++i) {
if (s[i] <= '9') continue;
for (s[i]='0'+(s[i]=='@'); s[i]<='9'; ++s[i]) {
memset(cache, -1, sizeof cache);
if (dp(0, 0)) break;
}
}
}
void eliminateZero(string& s) {
for (int i=0; i<s.size(); ++i) {
if (s[i] != '0') {
s = s.substr(i);
return;
} else if (i + 1 == s.size()) {
s = "0";
}
}
}
int main() {
int T;
scanf("%d", &T);
for (int N=1; N<=T; ++N) {
char eq;
scanf("%s %c %s = %s ", dat+0, &op, dat+1, dat+2);
a = dat[0]; b = dat[1]; c = dat[2];
len = max(max(a.size(), b.size()), c.size());
process(a); process(b); process(c);
calculate(a); calculate(b); calculate(c);
eliminateZero(a); eliminateZero(b); eliminateZero(c);
printf("Case #%d: ", N);
printf("%s %c %s = %s\n", a.c_str(), op, b.c_str(), c.c_str());
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
1584 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
235 ms |
1584 KB |
Output is correct |
