Submission #4070

#	Time	Username	Problem	Language	Result	Execution time	Memory
4070		sjw0687	계산식 복원 (GCJ12KOR_formula)	C++98	40 / 40	956 ms	1680 KiB

B

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;

int last1, last2, last3;
vector<int> num1, num2, num3;
char oper;
int len;

void strToVec(string& input, vector<int>& num)
{
	num.resize(input.size());
	for(int i=(int)input.size()-1; i>=0; i--) {
		int pos = (int)input.size()-1 - i;
		if(input[i] == '?')
			num[pos] = -1;
		else
			num[pos] = input[i] - '0';
	}
}

void printNum(vector<int>& num)
{
	int start = num.size()-1;
	while(num[start] == 0 && start > 0)
		start--;
	for(int i=start; i>=0; i--)
		cout << num[i];
}

vector<bool> possible[2];
bool isPossible()
{
	int len = max(last1, max(last2, last3))+1;
	possible[0].resize(len); possible[1].resize(len);
	fill(possible[0].begin(), possible[0].end(), false);
	fill(possible[1].begin(), possible[1].end(), false);

	if( oper == '+' ) {

		for(int i=0; i<len; i++) {

			int a, b, c;
			int v1, v2, v3;

			// no-carry
			v1 = num1[i];
			v2 = num2[i];
			v3 = num3[i];
			for(a=0; a<=9; a++) {
				if( v1 != -1 && a != v1 ) continue;
				if( a == 0 && i == last1 && i > 0) continue;

				for(b=0; b<=9; b++) {
					if( v2 != -1 && b != v2 ) continue;
					if( b == 0 && i == last2 && i > 0) continue;

					for(c=0; c<=9; c++) {
						if( v3 != -1 && c != v3 ) continue;
						if( c == 0 && i == last3 && i > 0) continue;

						// from no-carry
						if( i == 0 || possible[0][i-1] ) {
							if(a + b == c) {
								possible[0][i] = true;
								goto CODE_PLUS_NO_CARRY;
							}
						}

						// from carry
						if( i != 0 && possible[1][i-1]) {
							if(a + b + 1 == c) {
								possible[0][i] = true;
								goto CODE_PLUS_NO_CARRY;
							}
						}
					}
				}
			}
			CODE_PLUS_NO_CARRY:

			// carry
			if( i == len-1 ) continue;
			v1 = num1[i];
			v2 = num2[i];
			v3 = num3[i];

			for(a=0; a<=9; a++) {
				if( v1 != -1 && a != v1 ) continue;
				if( a == 0 && i == last1 && i > 0) continue;

				for(b=0; b<=9; b++) {
					if( v2 != -1 && b != v2 ) continue;
					if( b == 0 && i == last2 && i > 0) continue;

					for(c=0; c<=9; c++) {
						if( v3 != -1 && c != v3 ) continue;
						if( c == 0 && i == last3 && i > 0) continue;

						// from no-carry
						if( i == 0 || possible[0][i-1] ) {
							if(a + b - 10 == c) {
								possible[1][i] = true;
								goto CODE_PLUS_CARRY;
							}
						}

						// from carry
						if( i != 0 && possible[1][i-1]) {
							if(a + b - 10 + 1 == c) {
								possible[1][i] = true;
								goto CODE_PLUS_CARRY;
							}
						}
					}
				}
			}
			CODE_PLUS_CARRY:;

		}

		if(possible[0][len-1])
			return true;
		else
			return false;

	}
	else {

		for(int i=len-1; i>=0; i--) {

			int a, b, c;
			int v1, v2, v3;

			// no-carry
			v1 = num1[i];
			v2 = num2[i];
			v3 = num3[i];
			for(a=0; a<=9; a++) {
				if( v1 != -1 && a != v1 ) continue;
				if( a == 0 && i == last1 && i > 0) continue;

				for(b=0; b<=9; b++) {
					if( v2 != -1 && b != v2 ) continue;
					if( b == 0 && i == last2 && i > 0) continue;

					for(c=0; c<=9; c++) {
						if( v3 != -1 && c != v3 ) continue;
						if( c == 0 && i == last3 && i > 0) continue;

						// from no-carry
						if( i == len-1 || possible[0][i+1] ) {
							if(a - b == c) {
								possible[0][i] = true;
								goto CODE_MINUS_NO_CARRY;
							}
						}

						// from carry
						if( i != len-1 && possible[1][i+1]) {
							if(a - b + 10 == c) {
								possible[0][i] = true;
								goto CODE_MINUS_NO_CARRY;
							}
						}
					}
				}
			}
			CODE_MINUS_NO_CARRY:

			// carry
			if( i == 0 ) continue;
			v1 = num1[i];
			v2 = num2[i];
			v3 = num3[i];

			for(a=0; a<=9; a++) {
				if( v1 != -1 && a != v1 ) continue;
				if( a == 0 && i == last1 && i > 0) continue;

				for(b=0; b<=9; b++) {
					if( v2 != -1 && b != v2 ) continue;
					if( b == 0 && i == last2 && i > 0) continue;

					for(c=0; c<=9; c++) {
						if( v3 != -1 && c != v3 ) continue;
						if( c == 0 && i == last3 && i > 0) continue;

						// from no-carry
						if( i == len-1 || possible[0][i+1] ) {
							if(a - b - 1 == c) {
								possible[1][i] = true;
								goto CODE_MINUS_CARRY;
							}
						}

						// from carry
						if( i != len-1 && possible[1][i+1]) {
							if(a - b - 1 + 10 == c) {
								possible[1][i] = true;
								goto CODE_MINUS_CARRY;
							}
						}
					}
				}
			}
			CODE_MINUS_CARRY:;

		}

		if(possible[0][0])
			return true;
		else
			return false;

	}
}

int main(void)
{
	int cases;
	cin >> cases;
	string input;
	for(int tc=1; tc<=cases; tc++) {
		char tmp;

		cin >> input;
		strToVec(input, num1);
		cin >> oper;
		cin >> input;
		strToVec(input, num2);
		cin >> tmp;
		cin >> input;
		strToVec(input, num3);
		last1 = num1.size()-1; last2 = num2.size()-1; last3 = num3.size()-1;
		len = max(num1.size(), max(num2.size(), num3.size()));
		num1.resize(len, 0); num2.resize(len, 0); num3.resize(len, 0);

		for(int i=num1.size()-1; i>=0; i--) {
			if(num1[i] != -1) continue;
			for(int v=0; v<=9; v++) {
				if(v == 0 && i == last1 && i > 0) continue;
				num1[i] = v;
				if( isPossible() )
					break;
			}
		}
		for(int i=num2.size()-1; i>=0; i--) {
			if(num2[i] != -1) continue;
			for(int v=0; v<=9; v++) {
				if(v == 0 && i == last2 && i > 0) continue;
				num2[i] = v;
				if( isPossible() )
					break;
			}
		}
		for(int i=num3.size()-1; i>=0; i--) {
			if(num3[i] != -1) continue;
			for(int v=0; v<=9; v++) {
				if(v == 0 && i == last3 && i > 0) continue;
				num3[i] = v;
				if( isPossible() )
					break;
			}
		}

		cout << "Case #" << tc << ": ";

		printNum(num1);
		cout << ' ' << oper << ' ';
		printNum(num2);
		cout << " = ";
		printNum(num3);

		cout << endl;
	}
	return 0;
}

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