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_1, b_1, c_1\), 使得 \(a_1 + b_1 = c_1\). 比如在刚才的例子中, 可以这样重排:\(a_1 = 0111, b_1 = 0011, c_1 = 1010\). 你的任务是让 \(c_1\) 最小. 如果无解, 输出 \(-1\).

Input

输入仅一行, 包含三个整数 \(a, b, c\).

Output

输出仅一行, 为 \(c_1\) 的最小值.

Sample Input

7 6 9

Sample Output

10

Data Range

\(a, b, c \leq 2^{30}\)

Explanation

这道题看上去就和 \(a, b, c\) 一点关系没有.

然后统计一下 \(a, b, c\) 里面的 1 的个数, 就变成了一个 DP 问题. 简单建一个五维数组, 然后考虑上进位问题瞎搞一发 AC

结果一个 1 << n 挑了好久发现不停地输出 -2147483648, 后来才发现如果要进行高精度位运算地移位问题需要考虑到 long long, 然后正确的写法应该是 1ll << n. 这一点应该在以后的代码中留心.

内存强迫症请使用滚动数组

被 3106 错交了两次的题目表示莫名躺枪~

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(__var,__begin,__end) for(lli __var=__begin;__var<=__end;__var++)
#define minimize(__ref,__val) __ref=min(__ref,__val);
#define dig(__n) (1ll<<(__n))
using namespace std;
typedef long long lli;
const int maxn = 40;

lli get_available_digits(lli in) { lli res = 0;
    while (in) res += in & 1, in >>= 1; return res; }
lli get_digits(lli in) { lli res = 0;
    while (in) res++, in >>= 1; return res; }
template <typename _T>
_T max_3(_T __x, _T __y, _T __z) { return max(max(__x, __y), __z); }

lli v_a, v_b, v_c, n, a, b, c;
lli dp_arr[maxn][maxn][maxn][maxn][2];
#define dp(__t,__i,__j,__k,__l) dp_arr[__t][__i][__j][__k][__l]

int main(int argc, char** argv)
{
    // v_a, v_b, v_c are actual values.
    scanf("%lld%lld%lld", &v_a, &v_b, &v_c);
    // Maximum length of a, b, c
    n = max_3(get_digits(v_a), get_digits(v_b), get_digits(v_c));
    // Get existent 1s in a, b, c
    a = get_available_digits(v_a);
    b = get_available_digits(v_b);
    c = get_available_digits(v_c);
    // Resolved data, dynamic programming.
    // dp[t][i][j][k][l] = Counted t digits, i 1s in A, j 1s in B, k 1s in C,
    //     with l indicating whether last digits was an incrementation
    lli max_bound = 1ll << (n + 1);
    // printf("%lld %lld\n", n, max_bound);
    // Cleaning area...
    rep(t, 0, n) rep(i, 0, a) rep(j, 0, b) rep(k, 0, c)
        dp(t, i, j, k, 0) = dp(t, i, j, k, 1) = max_bound;
    dp(0, 0, 0, 0, 0) = 0;
    // Main procedure of dynamic programming.
    rep(t, 0, n - 1) rep(i, 0, min(a, t)) rep(j, 0, min(b, t)) rep(k, 0, min(c, t)) {
        // No addition, without increment @ here
        minimize( dp(t + 1, i, j, k, 0), dp(t, i, j, k, 0) );
        // No addition, with increment @ here
        minimize( dp(t + 1, i, j, k + 1, 0), dp(t, i, j, k, 1) );
        // Single addition, without increment @ here
        minimize( dp(t + 1, i + 1, j, k + 1, 0), dp(t, i, j, k, 0) + dig(t) );
        minimize( dp(t + 1, i, j + 1, k + 1, 0), dp(t, i, j, k, 0) + dig(t) );
        // Single addition, with increment @ here
        minimize( dp(t + 1, i + 1, j, k, 1), dp(t, i, j, k, 1) + dig(t) );
        minimize( dp(t + 1, i, j + 1, k, 1), dp(t, i, j, k, 1) + dig(t) );
        // Double addition, without increment @ here
        minimize( dp(t + 1, i + 1, j + 1, k, 1), dp(t, i, j, k, 0) + dig(t + 1) );
        // Double addition, with increment @ here
        minimize( dp(t + 1, i + 1, j + 1, k + 1, 1), dp(t, i, j, k, 1) + dig(t + 1) );
    }
    // Get final result
    lli res = dp(n, a, b, c, 0);
    if (res >= max_bound)
        res = -1;
    printf("%lld\n", res);
    return 0;
}