結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー GOTKAKO
提出日時 2025-10-31 22:22:35
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 2 ms / 6,000 ms
コード長 1,433 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,229 ms
コンパイル使用メモリ 203,520 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-31 22:22:39
合計ジャッジ時間 3,649 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 81181819;
    int T; cin >> T;
    while(T--){
        int N; cin >> N;
        N = n-N;
        int best = 1000;
        pair<vector<int>,vector<int>> memo;
        vector<int> One(10),Eight(10);
        bool ok = false;
        auto dfs = [&](auto dfs,int left,int now=0,int d=0) -> void {
            if(best <= now) return;
            if(left < 0) return;
            if(left == 0){
                best = now,memo = {One,Eight};
                return;
            }
            for(int one=0; one<=7; one++) for(int eight=0; one+eight<=7; eight++){
                int v = one+eight*8;
                One.at(d) = one,Eight.at(d) = eight;
                if((left-v)%10 == 0) dfs(dfs,(left-v)/10,max(now,one+eight),d+1);
                One.at(d) = 0,Eight.at(d) = 0;
            }
        };
        dfs(dfs,N);
        
        tie(One,Eight) = memo;
        vector<int> answer;
        while(true){
            long long now = 0;
            for(int i=8; i>=0; i--){
                now *= 10;
                if(One.at(i)) One.at(i)--,now++;
                else if(Eight.at(i)) Eight.at(i)--,now+=8;  
            }
            if(now == 0) break;
            answer.push_back(now);
        }

        cout << answer.size() << "\n";
        for(auto a : answer) cout << a << "\n";
    }
}
0