4fd800b3a8 2011-02-23        kinaba: #include <iostream>
4fd800b3a8 2011-02-23        kinaba: #include <string>
4fd800b3a8 2011-02-23        kinaba: #include <map>
4fd800b3a8 2011-02-23        kinaba: using namespace std;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: string err = "222222222222222222222222222222222222222222222222";
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: void operator&=( string& x, const string& r )
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	if( x.size() > r.size() )
4fd800b3a8 2011-02-23        kinaba: 		x = r;
4fd800b3a8 2011-02-23        kinaba: 	else if( x.size()==r.size() && x > r )
4fd800b3a8 2011-02-23        kinaba: 		x = r;
4fd800b3a8 2011-02-23        kinaba: }
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: struct BinarySum
4fd800b3a8 2011-02-23        kinaba: {
4fd800b3a8 2011-02-23        kinaba: 	map<int, string> memo;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	int rearrange(int a, int b, int c)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		int an=0,bn=0,cn=0,n=0;
4fd800b3a8 2011-02-23        kinaba: 		for(unsigned int i=1,t=1; i<=a; i<<=1,++t) {if(a&i) an++; n=max<int>(n,t);}
4fd800b3a8 2011-02-23        kinaba: 		for(unsigned int i=1,t=1; i<=b; i<<=1,++t) {if(b&i) bn++; n=max<int>(n,t);}
4fd800b3a8 2011-02-23        kinaba: 		for(unsigned int i=1,t=1; i<=c; i<<=1,++t) {if(c&i) cn++; n=max<int>(n,t);}
4fd800b3a8 2011-02-23        kinaba: 		string ans = err;
4fd800b3a8 2011-02-23        kinaba: 		ans &= mini( 0, cn-1, an-1, bn   ); // 1+0(+0)=01
4fd800b3a8 2011-02-23        kinaba: 		ans &= mini( 0, cn-1, an,   bn-1 ); // 0+1(+0)=01
4fd800b3a8 2011-02-23        kinaba: 		ans &= mini( 1, cn-1, an,   bn );   // 0+0(+1)=01
4fd800b3a8 2011-02-23        kinaba: 		if( ans.find('2') != string::npos )
4fd800b3a8 2011-02-23        kinaba: 			return -1;
4fd800b3a8 2011-02-23        kinaba: 		ans = "1"+ans;
4fd800b3a8 2011-02-23        kinaba: 		if( ans.size() > n )
4fd800b3a8 2011-02-23        kinaba: 			return -1;
4fd800b3a8 2011-02-23        kinaba: 		int v = 0;
4fd800b3a8 2011-02-23        kinaba: 		for(int i=0; i<ans.size(); ++i)
4fd800b3a8 2011-02-23        kinaba: 			v = (v<<1) | (ans[i] - '0');
4fd800b3a8 2011-02-23        kinaba: 		return v;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 	string mini(int d, int cn, int an, int bn)
4fd800b3a8 2011-02-23        kinaba: 	{
4fd800b3a8 2011-02-23        kinaba: 		if( cn<0 || an<0 || bn<0 )
4fd800b3a8 2011-02-23        kinaba: 			return err;
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		int key = (cn<<24)+(an<<16)+(bn<<8)+d;
4fd800b3a8 2011-02-23        kinaba: 		if( memo.count(key) )
4fd800b3a8 2011-02-23        kinaba: 			return memo[key];
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		if( d==0 && cn==0 && an==0 && bn==0 )
4fd800b3a8 2011-02-23        kinaba: 			return "";
4fd800b3a8 2011-02-23        kinaba: 
4fd800b3a8 2011-02-23        kinaba: 		string ans = err;
4fd800b3a8 2011-02-23        kinaba: 		if( d == 0 ) {
4fd800b3a8 2011-02-23        kinaba: 			ans &= "1"+mini( 0, cn-1, an-1, bn ); // 1+0(+0)=01
4fd800b3a8 2011-02-23        kinaba: 			ans &= "1"+mini( 0, cn-1, an, bn-1 ); // 0+1(+0)=01
4fd800b3a8 2011-02-23        kinaba: 			ans &= "1"+mini( 1, cn-1, an, bn );   // 0+0(+1)=01
4fd800b3a8 2011-02-23        kinaba: 		} else {
4fd800b3a8 2011-02-23        kinaba: 			ans &= "0"+mini( 0, cn, an-1, bn-1 ); // 1+1(+0)=10
4fd800b3a8 2011-02-23        kinaba: 			ans &= "0"+mini( 1, cn, an-1, bn );   // 1+0(+1)=10
4fd800b3a8 2011-02-23        kinaba: 			ans &= "0"+mini( 1, cn, an, bn-1 );    // 0+1(+1)=10
4fd800b3a8 2011-02-23        kinaba: 			ans &= "1"+mini( 1, cn-1, an-1, bn-1 ); // 1+1(+1)=11
4fd800b3a8 2011-02-23        kinaba: 		}
4fd800b3a8 2011-02-23        kinaba: 		return memo[key] = ans;
4fd800b3a8 2011-02-23        kinaba: 	}
4fd800b3a8 2011-02-23        kinaba: };