Codeforces Round #624 (Div. 3) D 题

题目链接:Three Integers

简要题意:

给出 \(a, b, c\) 满足 \(a \leq b \leq c\)。

你可以随便选择其中一个数,使这个数 \(+1\) 或 \(-1\)。

假设最后操作完 \(a\) 为 \(A\),\(b\) 为 \(B\),\(c\) 为 \(C\)。

你需要使 \(A | B\) 且 \(B | C\),并最小化操作次数。

输出操作次数和 \(A, B, C\)。

多组数据。

数据范围:\(1 \leq t \leq 100\),\(1 \leq a, b, c \leq 10 ^ 4\)。

做法

考虑到最后的 \(A, B, C\) 一定满足 \((a1 \cdot A = B\) 且 \(a2 \cdot B = C)\) 其中 \(a1, a2 \geq 1\) 且为整数。

根据 \(a1 \cdot A = B\) 和 \(a2 \cdot B = C\) 可得 \(C = a1 \cdot ca2 \cdot A\)。

故我们只需枚举 \(A, a1, a2\) 然后求出 \(A, B, C\) 并与 \(a, b, c\) 比较取最小值即可。

考虑到 \(1 \leq a, b, c \leq 10 ^ 4\),可知 \(A, B, C \leq 3 \times 4000\)。

故枚举不会超时。

Code:

#include <bits/stdc++.h>
 
#define ll long long
#define rep(i, l, r) for (int i = l; i <= r; ++ i)
 
using namespace std;
 
inline int read() {
    int cnt = 0, opt = 1; char ch = getchar();
 
    for (; ! isdigit(ch); ch = getchar()) 
        if (ch == '-')  opt = 0;
    for (; isdigit(ch); ch = getchar()) 
        cnt = (cnt << 1) + (cnt << 3) + (ch ^ 48);
 
    return opt ? cnt : -cnt;
}
 
int T;  
 
int main() {
    T = read();
    while (T --) {
        long long a, b, c, a1, a2, a3;
        long long ans = (1ll << 60);
        a = read(), b = read(), c = read();
        rep (i, 1, 12000)
            rep (j, 1, 12000 / i + 1)
                rep (k, 1, 12000 / (i * j) + 2)
                    if (ans > abs(i - a) + abs(1ll * i * j - b) + abs(1ll * i * j * k - c))
                        ans = abs(i - a) + abs(1ll * i * j - b) + abs(1ll * i * j * k - c), 
                         a1 = i, a2 = i * j, a3 = i * j * k;
 
            cout << ans << endl << a1 << ' ' << a2 << ' ' << a3 << endl;
    }
    return 0;
}
上一篇:C - Longge's problem


下一篇:【进阶指南学习笔记】lowbit