Description
输入三个整数\(a, b, c\)，把它们写成无前导\(0\)的二进制整数。比如\(a=7, b=6, c=9\)，写成二进制为\(a=111, b=110, c=1001\)。接下来以位数最多的为基准，其他整数在前面添加前导\(0\)，使得\(a, b, c\)拥有相同的位数。比如在刚才的例子中，添加完前导\(0\)后为\(a=0111, b=0110, c=1001\)。最后，把\(a, b, c\)的各位进行重排，得到\(a’, b’, c’\)，使得\(a’+b’=c’\)。比如在刚才的例子中，可以这样重排：\(a’=0111, b’=0011, c’=1010\)。
你的任务是让\(c’\)最小。如果无解，输出\(-1\)。
Input
输入仅一行，包含三个整数\(a, b, c\)。
Output
输出仅一行，为\(c’\)的最小值。
Sample Input
7 6 9
Sample Output
10
HINT
\(a,b,c \le 2^{30}\)
自己难得看出来一道高维的\(dp\)题目：\(f[i][j][k][l][m]\)表示前\(i\)位二进制数中，\(a’\)用了\(j\)个1，\(b’\)用了\(k\)个\(1\)，合成的\(c’\)在前\(i\)位中有\(l\)个\(1\)。
于是，根据二进制加法，我们可以得到\(dp\)方程：
\[f[i+1][j+1][k][l+1][0] = min(f[i+1][j+1][k][l+1][0],f[i][j][k][l][0] \mid (1 \ll i))
\]
\]
\[f[i+1][j+1][k][l][1] = min(f[i+1][j+1][k][l][1],f[i][j][k][l][1])
\]
\]
\[f[i+1][j][k+1][l+1][0] = min(f[i+1][j][k+1][l+1][0],f[i][j][k][l][0] \mid (1 \ll i))
\]
\]
\[f[i+1][j][k+1][l][1] = min(f[i+1][j][k+1][l][1],f[i][j][k][l][1])
\]
\]
\[f[i+1][j+1][k+1][l][1] = min(f[i+1][j+1][k+1][l][1],f[i][j][k][l][0])
\]
\]
\[f[i+1][j+1][k+1][l+1][1] = min(f[i+1][j+1][k+1][l+1][1],f[i][j][k][l][1] \mid (1 \ll i))
\]
\]
\[f[i+1][j][k][l+1][0] = min(f[i+1][j][k][l+1][0],f[i][j][k][l][1] \mid (1 \ll i))
\]
\]
\[f[i+1][j][k][l][0] = min(f[i+1][j][k][l][0],f[i][j][k][l][0])
\]
\]
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef long long ll;
#define maxn (35)
ll a,b,c,f[maxn][maxn][maxn][maxn][2];
int n,w1,w2,w3;
inline void ready()
{
memset(f,0x7,sizeof(f));
f[0][0][0][0][0] = 0;
int cnt,i;
for (i = a,cnt = 0;i;i >>= 1,++cnt) if (i & 1) ++w1;
n = max(n,cnt);
for (i = b,cnt = 0;i;i >>= 1,++cnt) if (i & 1) ++w2;
n = max(n,cnt);
for (i = c,cnt = 0;i;i >>= 1,++cnt) if (i & 1) ++w3;
n = max(n,cnt);
}
inline void dp()
{
for (int i = 0;i < n;++i)
for (int j = 0;j <= i&&j <= w1;++j)
for (int k = 0;k <= i&&k <= w2;++k)
for (int l = 0;l <= i&&l <= w3;++l)
{
if (j < w1)
{
if (l < w3) f[i+1][j+1][k][l+1][0] = min(f[i+1][j+1][k][l+1][0],f[i][j][k][l][0]|(1<<i));
f[i+1][j+1][k][l][1] = min(f[i+1][j+1][k][l][1],f[i][j][k][l][1]);
}
if (k < w2)
{
if (l < w3) f[i+1][j][k+1][l+1][0] = min(f[i+1][j][k+1][l+1][0],f[i][j][k][l][0]|(1<<i));
f[i+1][j][k+1][l][1] = min(f[i+1][j][k+1][l][1],f[i][j][k][l][1]);
}
if (j < w1&&k < w2)
{
f[i+1][j+1][k+1][l][1] = min(f[i+1][j+1][k+1][l][1],f[i][j][k][l][0]);
if (l < w3) f[i+1][j+1][k+1][l+1][1] = min(f[i+1][j+1][k+1][l+1][1],f[i][j][k][l][1]|(1<<i));
}
if (l < w3) f[i+1][j][k][l+1][0] = min(f[i+1][j][k][l+1][0],f[i][j][k][l][1]|(1<<i));
f[i+1][j][k][l][0] = min(f[i+1][j][k][l][0],f[i][j][k][l][0]);
}
}
int main()
{
freopen("3107.in","r",stdin);
freopen("3107.out","w",stdout);
scanf("%lld %lld %lld",&a,&b,&c);
ready();
dp();
if (f[n][w1][w2][w3][0] > (1ll<<40)) printf("-1");
else printf("%lld",f[n][w1][w2][w3][0]);
fclose(stdin); fclose(stdout);
return 0;
}