結果

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

ソースコード

diff #
raw source code 

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define ll 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<int> dpf(81181820, -1);
    vector<short> dps(81181820, 30000);
    dpf[0] = 0; dps[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>=dpf.size())break;
        cand.push_back(now);
        dpf[now] = now;
        dps[now] = 1;
    }
    rep(i, dpf.size()){
        if(i==0)continue;
        int idx = 0;
        while(cand[idx]<=dpf[i]){
            if(i+cand[idx]>=dpf.size())break;
            if(dps[i+cand[idx]]>dps[i]+1){
                dps[i+cand[idx]] = dps[i]+1;
                dpf[i+cand[idx]] = cand[idx];
            }
            else if(dps[i+cand[idx]]==dps[i]+1&&dpf[i+cand[idx]]>cand[idx]){
                dpf[i+cand[idx]] = cand[idx];
            }
            else break;
            idx++;
        }
    }
    rep(i, t){
        int N;
        cin >> N;
        N = 81181819-N;
        cout << dps[N] << endl;
        while(N){
            cout << dpf[N] << endl;
            N-=dpf[N];
        }
    }
    return 0;
}
0