Submission #13822

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

B

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

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