結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー Rumain831
提出日時 2025-10-31 23:35:09
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,970 bytes
コンパイル時間 1,128 ms
コンパイル使用メモリ 87,132 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-10-31 23:35:14
合計ジャッジ時間 5,111 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 10 WA * 12
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
using ll = long long;

int main(void){
  ll mx=81181819;
  vector<ll> Ten(10, 1);
  for(int i=1; i<10; i++) Ten[i]=Ten[i-1]*10ll;
  int t; cin >> t;
  while(t--){
    ll n; cin >> n;
    ll tar=mx-n;
    if(tar<8){
      cout << tar << endl;
      for(int i=0; i<tar; i++) cout << 1 << endl;
      continue;
    }
    else if(tar<10){
      cout << tar-7 << endl;
      if(tar==8) cout << 8 << endl;
      else cout << 1 << endl << 8 << endl;
      continue;
    }
    int d=to_string(tar).size(), Max=10;
    vector<vector<ll>> ans(10);
    auto DFS=[&](auto DFS, int di, ll now, ll maxi, vector<vector<ll>> path){
      //cout << di << ' ' << now << ' ' << maxi << endl;
      if(di==0){
        if(now==0&&Max>maxi){
          Max=maxi, ans=path;
        }
        return;
      }
      ll ten=Ten[di-1];
      if(now/ten>=100) return;
      {//ten, ten, ..., ten
        for(ll i=0; i<=7; i++){
          if(ten*i>now) break;
          if(i) path[di].push_back(ten);
          //cout << di << ' ' << now << ' ' << i << ' ' << now-i*ten << ' ' << ten << endl;
          DFS(DFS, di-1, now-i*ten, max(maxi, i), path);
        }
      }
      path[di].clear();
      {//8*ten, 8*ten, ..., ten
        for(ll i=1; i<=7; i++){
          if(ten*(8*i)>now) break;
          vector<ll> pa(i, 8*ten);
          path[di]=pa;
          for(ll j=0; j<2; j++){
            if(ten*(8*i+j)>now) break;
            if(j) path[di].push_back(ten);
            DFS(DFS, di-1, now-ten*(8*i+j), max(maxi, i+j), path);
          }
        }
      }
    };
    vector<vector<ll>> emp(10);
    DFS(DFS, d, tar, 0, emp);
    cout << Max << endl;
    // for(auto p:ans){
    //   for(auto q:p) cout << q << ' '; cout << endl;
    // }
    for(int i=0; i<Max; i++){
      ll num=0;
      for(int j=0; j<10; j++){
        if(ans[j].size()>i) num+=ans[j][i];
      }
      cout << num << endl;
    }
  }
  return 0;
}
0