結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー shingo0909
提出日時 2025-10-31 22:20:46
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 6,000 ms
コード長 1,911 bytes
コンパイル時間 3,368 ms
コンパイル使用メモリ 289,448 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-10-31 22:20:51
合計ジャッジ時間 4,587 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;

int main(){
    int t;
    cin >> t;
    while(t--){
        ll p;
        cin >> p;
        p=81181819-p;
        vector<int>x(8);
        for(int i=0;i<8;i++){
            x[7-i]=p%10;
            p/=10;
        }
        vector<vector<int>>dp(9,vector<int>(10,100));
        vector<vector<int>>prev(9,vector<int>(10,-1));
        dp[0][0]=0;
        for(int i=0;i<8;i++){
            for(int j=0;j<10;j++)
            for(int k=0;k<10;k++){
                int cur=j*10+x[i]-k;
                if(cur<0)continue;
                int cnt=cur/8+cur%8;
                int nx=max(dp[i][j],cnt);
                if(dp[i+1][k]>nx){
                    dp[i+1][k]=nx;
                    prev[i+1][k]=j;
                }
            }
        }
        cout << dp[8][0] << endl;
        int b=0;
        vector<int>rem;
        for(int i=8;i>0;i--){
            rem.push_back(b);
            b=prev[i][b];
        }
        reverse(rem.begin(),rem.end());
        vector<int>ans(8);
        for(int i=0;i<8;i++){
            if(i!=0)ans[i]=rem[i-1]*10+x[i]-rem[i];
            else ans[i]=x[i]-rem[i];
        }
        vector<string> out;
        while(true){
            out.push_back("");
            for(int i=0;i<8;i++){
                if(ans[i]>=8){
                    out.back().push_back('8');
                    ans[i]-=8;
                }else if(ans[i]>=1){
                    out.back().push_back('1');
                    ans[i]-=1;
                }else{
                    out.back().push_back('0');
                }
            }
            bool ok=true;
            for(int i=0;i<8;i++)if(ans[i]!=0)ok=false;
            if(ok)break;
        }
        for(string &s:out){
            while(s[0]=='0')s.erase(s.begin());
            cout << s << endl;
        }
    }
    return 0;
}
0