AOJ - Problem 0110 : Alphametic

• 問題文

覆面算の問題です。Xの部分に0-9のどれかの数字が入るので10通り調べるとよいです。数値に変換するとオーバフローするので文字列のまま足し算しましょう。多倍長整数が標準で存在する言語だと楽ができることでしょう。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string plus_string(string a, string b){
	string c;
	reverse( a.begin() , a.end() );
	reverse( b.begin() , b.end() );
	while( a.size() != b.size() ){
		if( a.size() < b.size() ){
			a.push_back('0');
		}else{
			b.push_back('0');
		}
	}
	for(int i=0 ; i < a.size() ; i++ ){
		c.push_back('0');
	}
	int n=0;
	for(int i=0 ; i < a.size() ; i++ ){
		if( n+a[i]+b[i]-'0'-'0' <= 9 ){
			c[i] = a[i] + b[i] - '0' + n;
			n = 0;
		}else{
			c[i] = a[i] + b[i] - '0' - 10 + n;
			n = 1;
		}
	}
	if( n == 1 ){
		c.push_back( '1' );
	}
	reverse( c.begin() , c.end() );
	return c;
}

string change_X(string s, char c){
	for(int i=0 ; i < s.size() ; i++ ){
		if( s[i] == 'X' ){
			s[i] = c;
		}
	}
	return s;
}

void solve(string s){
	string num1, num2, num3, a, b, c;
	int plus, equal;
	for(int i=0 ; i < s.size() ; i++ ){
		if( s[i] == '+' )
			plus = i;
		if( s[i] == '=' )
			equal = i;
	}
	num1 = s.substr( 0 , plus );
	num2 = s.substr( plus+1 , equal-plus-1 );
	num3 = s.substr( equal+1 );
	for(int i=0 ; i <= 9 ; i++ ){
		a = change_X( num1 , i+'0' );
		b = change_X( num2 , i+'0' );
		c = change_X( num3 , i+'0' );
		if( plus_string( a , b ) == c ){
			cout << i << endl;
			return;
		}
	}
	cout << "NA" << endl;
}

int main(){
	string s;
	while( cin >> s ){
		solve( s );
	}
}