#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
string a, b, c;
char aa[2][250], bb[2][250], cc[2][250];
int cache[2][250], way[2][250];
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, char op) {
int &ret = cache[carry][pos];
if (~ret) return ret;
int &n = way[carry][pos] = 0;
if (pos+1 < a.size()) {
if (dp(0, pos+1, op) && dp(1, pos+1, op)) {
n = -1;
} else if (dp(1, pos+1, op)) {
n = 1;
} else if (!(dp(0, pos+1, op)))
return ret = 0;
}
char &x = aa[carry][pos], &y = bb[carry][pos], &z = cc[carry][pos];
int minx = minv(a[pos]), miny = minv(b[pos]), minz = minv(c[pos]);
int maxx = maxv(a[pos]), maxy = maxv(b[pos]), maxz = maxv(c[pos]);
int minn = ~n ? n : 0, maxn = ~n ? n : 1;
for (x = minx; x <= maxx; ++x)
for (y = miny; y <= maxy; ++y)
for (n = minn; n <= maxn; ++n) {
if (op == '+') z = x + y - '0' - carry*10 + n;
else z = x - y + '0' + carry*10 - n;
if (z >= minz && z <= maxz) return ret = 1;
}
return ret = 0;
}
inline void process(string& s, int len) {
if (s[0] == '?' && s.size() > 1) s[0] = '@';
s = string(len - s.size(), '0') + s;
}
void calculate(string& s, char op) {
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, op)) 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() {
ios::sync_with_stdio(false);
int T;
cin >> T;
for (int N=1; N<=T; ++N) {
char op, eq;
cin >> a >> op >> b >> eq >> c;
int len = max(max(a.size(), b.size()), c.size());
process(a, len); process(b, len); process(c, len);
calculate(a, op); calculate(b, op); calculate(c, op);
eliminateZero(a); eliminateZero(b); eliminateZero(c);
cout << "Case #" << N << ": ";
cout << a << ' ' << op << ' ' << b << ' ' << eq << ' ' << c << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
1720 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
265 ms |
1720 KB |
Output is correct |
