結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー 北杜
提出日時 2025-10-31 23:23:57
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,634 bytes
コンパイル時間 3,134 ms
コンパイル使用メモリ 283,816 KB
実行使用メモリ 814,464 KB
最終ジャッジ日時 2025-10-31 23:24:05
合計ジャッジ時間 6,363 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1
other -- * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define all(a) (a).begin(), (a).end()
const ll INF32 = 2e9;
const ll INF64 = 4e18;

void printYN(bool ok){
    if(ok)cout << "Yes" << endl;
    else cout << "No" << endl;
    return;
}

signed main() {
    int t;
    cin >> t;
    vector<pair<int, int>> dp(81181820, make_pair(-1, INF32));
    dp[0] = {0,0};
    vector<int> cand;
    rep(i, 3*3*3*3*3*3*3*3){
        if(i==0)continue;
        int ii = i;
        const vector<int> n = {0,1,8};
        int now = 0;
        rep(j, 8){
            int b = 1;
            rep(k, j)b*=10;
            now += b*n[ii%3];
            ii/=3;
        }
        if(now>=dp.size())break;
        cand.push_back(now);
        dp[now] = {now, 1};
    }
    rep(i, dp.size()){
        if(i==0)continue;
        int idx = 0;
        while(cand[idx]<=dp[i].first){
            if(i+cand[idx]>=dp.size())break;
            if(dp[i+cand[idx]].second>dp[i].second+1){
                dp[i+cand[idx]].second = dp[i].second+1;
                dp[i+cand[idx]].first = cand[idx];
            }
            else if(dp[i+cand[idx]].second==dp[i].second+1&&dp[i+cand[idx]].first>cand[idx]){
                dp[i+cand[idx]].first = cand[idx];
            }
            else break;
            idx++;
        }
    }
    rep(i, t){
        int N;
        cin >> N;
        N = 81181819-N;
        cout << dp[N].second << endl;
        while(N){
            cout << dp[N].first << endl;
            N-=dp[N].first;
        }
    }
    return 0;
}
0