結果

問題 No.3408 1215 Segments
コンテスト
ユーザー sclara
提出日時 2025-12-01 22:17:33
言語 C++23
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 727 ms / 2,500 ms
コード長 5,772 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,183 ms
コンパイル使用メモリ 289,316 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-12-14 23:36:18
合計ジャッジ時間 41,339 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

bool ckran(int a, int n) {
    return (a >= 0 && a < n);
}

template<typename T, typename U>
bool chmax(T& a, U b) {
    if (a < b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

template<typename T, typename U>
bool chmin(T& a, U b) {
    if (a > b) {
        a = b;
        return true;
    } else {
        return false;
    }
}

std::vector<long long> lltovec(long long n, long long base = 10, long long minsize = -1) {
    std::vector<long long> res;
    while (minsize-- > 0 || n > 0) {
        res.push_back(n % base);
        n /= base;
    }
    // std::reverse(res.begin(), res.end());
    return res;
}

long long vectoll(std::vector<long long> vec, long long base = 10) {
    long long res = 0;
    std::reverse(vec.begin(), vec.end());
    for (auto i : vec) {
        res *= base;
        res += i;
    }
    std::reverse(vec.begin(), vec.end());
    return res;
}

int main()
{
    long long n;
    cin >> n;
    vector<vector<long long>> candidate;
    vector<vector<long long>> default_segment = {
        {1, 1, 1, 1, 1, 1, 0},
        {0, 1, 1, 0, 0, 0, 0},
        {1, 1, 0, 1, 1, 0, 1},
        {1, 1, 1, 1, 0, 0, 1},
        {0, 1, 1, 0, 0, 1, 1},
        {1, 0, 1, 1, 0, 1, 1},
        {1, 0, 1, 1, 1, 1, 1},
        {1, 1, 1, 0, 0, 0, 0},
        {1, 1, 1, 1, 1, 1, 1},
        {1, 1, 1, 1, 0, 1, 1}
    };
    vector<long long> digits_frequency(10, 0);
    auto find_sets = [&](auto && self, long long cur, long long cc) -> void {
        if (cur == 10) {
            bool flag = true;
            vector<long long> segments_frequency(7, 0);
            for (int i = 0; i < 10; ++i) {
                for (int j = 0; j < 7; ++j) {
                    segments_frequency[j] += default_segment[i][j] * digits_frequency[i];
                }
            }
            long long use = segments_frequency[2] + segments_frequency[4];
            if (use % 2 != 0) flag = false;
            use /= 2;
            if (!ckran(use - segments_frequency[6], digits_frequency[0] + 1)) flag = false;
            segments_frequency[0] -= use - segments_frequency[6];
            segments_frequency[1] -= use - segments_frequency[6];
            segments_frequency[5] -= use - segments_frequency[6];
            segments_frequency[6] = use;
            if (!ckran(use - segments_frequency[4], digits_frequency[1] + 1)) flag = false;
            segments_frequency[1] -= use - segments_frequency[4];
            segments_frequency[2] -= use - segments_frequency[4];
            segments_frequency[5] += use - segments_frequency[4];
            segments_frequency[4] = use;
            if (!ckran(segments_frequency[0] - use, digits_frequency[6] + 1)) flag = false;
            segments_frequency[0] = use;
            if (!ckran(use - segments_frequency[5], digits_frequency[7] + 1)) flag = false;
            segments_frequency[5] = use;
            if (!ckran(segments_frequency[3] - use, digits_frequency[9] + 1)) flag = false;
            segments_frequency[3] = use;
            if (segments_frequency[1] != use || segments_frequency[2] != use) flag = false;
            if (flag) {
                for (int i = cc; i <= 19; ++i) {
                    digits_frequency[8] += i - cc;
                    candidate.push_back(digits_frequency);
                    digits_frequency[8] -= i - cc;
                }
            }
            return;
        }
        if (cur == 8) {
            self(self, cur + 1, cc);
            return;
        }
        for (int i = 0; i < 20 - cc; ++i) {
            digits_frequency[cur] = i;
            self(self, cur + 1, cc + i);
            digits_frequency[cur] = 0;
        }
    };
    find_sets(find_sets, 0, 0);
    auto vec_n = lltovec(n);
    long long n_size = vec_n.size();
    vec_n = lltovec(n, 10, 19);
    long long ans = 2e18;
    long long digits_count = 0;
    vector<long long> pl(19, 1);
    for (int i = 1; i < 19; ++i) {
        pl[i] = pl[i - 1] * 10;
    }
    auto find_minimum = [&](auto && self, vector<long long> digits_frequency, long long cur, long long cur_ans) -> void {
        if (digits_count < n_size) return;
        if (cur == -1) {
            chmin(ans, cur_ans);
        }
        if (cur_ans > n || cur > digits_count) {
            for (int i = 0; i < 10; ++i) {
                if (digits_frequency[i] > 0) {
                    digits_frequency[i]--;
                    cur_ans += pl[cur] * i;
                    self(self, digits_frequency, cur - 1, cur_ans);
                    break;
                }
            }
        } else {
            if (digits_frequency[vec_n[cur]] > 0 && !(cur_ans == 0 && vec_n[cur] == 0)) {
                if (cur == 18) cur_ans += pl[18] * min(2LL, vec_n[cur]);
                else cur_ans += pl[cur] * vec_n[cur];
                digits_frequency[vec_n[cur]]--;
                self(self, digits_frequency, cur - 1, cur_ans);
                if (cur == 18) cur_ans -= pl[18];
                else cur_ans -= pl[cur] * vec_n[cur];
                digits_frequency[vec_n[cur]]++;
            }
            for (int i = vec_n[cur] + 1; i < 10; ++i) {
                if (digits_frequency[i] > 0) {
                    if (cur == 18) cur_ans += pl[18] * min(2, i);
                    else cur_ans += pl[cur] * i;
                    digits_frequency[i]--;
                    self(self, digits_frequency, cur - 1, cur_ans);
                    break;
                }
            }
        }
    };
    for (int i = 0; i < (int)candidate.size(); ++i) {
        for (int j = 0; j < 10; ++j) digits_count += candidate[i][j];
        find_minimum(find_minimum, candidate[i], digits_count - 1, 0);
        digits_count = 0;
    }
    cout << ans << endl;
}
0