Codeforces 214B Hometask：從數字集合構造最大能被2、3、5整除的整數

問題重述

給定 n 個數字（0-9），選擇其中部分（可全選）組成一個整數，要求：

1. 無前導零（除非數字本身就是 0）。
2. 該數能被 2、3、5 同時整除（即能被 30 整除）。
3. 每個數字使用次數不超過給定次數。
4. 輸出滿足條件的最大整數，無解輸出 -1。

關鍵觀察

• 能被 2 和 5 整除 → 最後一位必須是 0。若無 0，直接輸出 -1。
• 能被 3 整除 → 所有數字之和模 3 為 0。
• 為使數字最大：按降序排列（高位盡量大）。

貪心調整策略

設所有數字和為 sum，cnt[d] 為數字 d 的出現次數。

1. 若 sum % 3 == 0：直接按降序輸出所有數字（0 在末尾）。
2. 若 sum % 3 == 1：
   • 優先刪除一個最小的 {1,4,7} 中存在的數字。
   • 若無，則刪除兩個最小的 {2,5,8} 中的數字（因 2+2=4≡1, 5+5=10≡1, 8+8=16≡1 mod 3）。
   • 若仍無法，無解。
3. 若 sum % 3 == 2：
   • 優先刪除一個最小的 {2,5,8}。
   • 否則刪除兩個最小的 {1,4,7}（1+1=2, 4+4=8≡2, 7+7=14≡2 mod 3）。
   • 否則無解。
4. 刪除後若剩餘數字全為 0，僅輸出單個 0。

代碼實現（C++）

#include 
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector cnt(10, 0);
        long long sum = 0;
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            cnt[x]++;
            sum += x;
        }
        if (cnt[0] == 0) {
            cout << -1 << '\n';
            continue;
        }
        auto remove_one = [&](const vector& digits) {
            for (int d : digits) if (cnt[d] > 0) { cnt[d]--; return true; }
            return false;
        };
        auto remove_two = [&](const vector& digits) {
            int removed = 0;
            for (int d : digits) {
                while (cnt[d] > 0 && removed < 2) { cnt[d]--; removed++; }
            }
            return removed == 2;
        };
        bool ok = true;
        if (sum % 3 == 1) {
            if (!remove_one({1,4,7}) && !remove_two({2,5,8})) ok = false;
        } else if (sum % 3 == 2) {
            if (!remove_one({2,5,8}) && !remove_two({1,4,7})) ok = false;
        }
        if (!ok) {
            cout << -1 << '\n';
            continue;
        }
        bool all_zero = true;
        for (int d = 1; d <= 9; ++d) if (cnt[d]) all_zero = false;
        if (all_zero) {
            cout << 0 << '\n';
        } else {
            for (int d = 9; d >= 0; --d)
                while (cnt[d]--) cout << d;
            cout << '\n';
        }
    }
    return 0;
}

複雜度分析

• 時間：O(n + 10) ≈ O(n)，僅涉及計數與常數次調整。
• 空間：O(1)，固定大小計數數組。

測試樣例

輸入: 1 0           → 輸出: 0
輸入: 11 3 4 5 4 5 3 5 3 4 4 0 → 輸出: 5554443330
輸入: 8 3 2 5 1 5 2 2 3        → 輸出: -1