結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー のらら
提出日時 2025-08-12 21:02:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,150 bytes
コンパイル時間 2,869 ms
コンパイル使用メモリ 179,240 KB
実行使用メモリ 7,724 KB
最終ジャッジ日時 2025-10-25 16:58:52
合計ジャッジ時間 5,811 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 21
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll kakeru[11];
ll minsize;
vector<ll> ans, tmpans;
void dfs(int pos, ll used, ll num, vector<ll> &iv){
  //cout << "dfs " << pos << " " << used << " " << num << endl;
  if(pos == -1){
    if(num > 0) return;
    if(used < minsize){
      minsize = used;
      ans = tmpans;
    }
    return;
  }
  
  ll rest = num * 10 + iv[pos];
  //8以上は無条件で使う
  ll cnt8 = rest / 8;
  if(cnt8 >= (int)ans.size()) return; //採用しない
  for(int i = 0; i < cnt8; i++){
    if(tmpans[i] == 0) used++;
    tmpans[i] += 8 * kakeru[pos];
  }
  for(int i = 0; i <= rest - 8 * cnt8; i++){
    if(cnt8 + i + 1 >= minsize) break;
    for(int j = 0; j < i; j++){
      if(tmpans[cnt8 + j] == 0) used++;
      tmpans[cnt8 + j] += kakeru[pos];
    }
    dfs(pos - 1, used, rest - 8 * cnt8 - i, iv);
    for(int j = i - 1; j >= 0; j--){
      tmpans[cnt8 + j] -= kakeru[pos];
      if(tmpans[cnt8 + j] == 0) used--;
    }
  }
  for(int i = cnt8 - 1; i >= 0; i--){
    tmpans[i] -= 8 * kakeru[pos];
    if(tmpans[i] == 0) used--;
  }
}

int main(){
  ll Q;
  cin >> Q;
  kakeru[0] = 1;
  for(int i = 1; i <= 10; i++) kakeru[i] = kakeru[i - 1] * 10;
  
  for(int q = 1; q <= Q; q++){
    ll N;
    cin >> N;
    ll X = 81181819 - N;
    vector<ll> v;
    while(X > 0){
      v.push_back(X % 10);
      X /= 10;
    }
    //貪欲解を作る
    ans.clear();
    for(int i = 0; i < (int)v.size(); i++){
      ll rest = v[i];
      ll st = 0;
      if(rest >= 8){
        if((int)ans.size() == 0) ans.push_back(8 * kakeru[i]);
        else ans[0] += 8 * kakeru[i];
        st++;
        rest -= 8;
      }
      for(int j = 0; j < rest; j++){
        if((int)ans.size() <= st + j) ans.push_back(kakeru[i]);
        else ans[st+j] += kakeru[i];
      }
    }
    minsize = ans.size();
    //cout << "chk " << minsize << endl;
    tmpans = vector<ll>(minsize, 0);
    dfs((int)v.size() - 1, 0, 0, v);
    cout << minsize << endl;
    for(int i = 0; i < minsize; i++) cout << ans[i] << endl;
  }
  return 0;
}
0