#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;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
1680 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
956 ms |
1680 KB |
Output is correct |
