Submission #13816

#	Time	Username	Problem	Language	Result	Execution time	Memory
13816		veckal	계산식 복원 (GCJ12KOR_formula)	C++14	40 / 40	265 ms	1720 KiB

B

#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;
}

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