結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー のらら
提出日時 2025-09-17 22:56:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,241 bytes
コンパイル時間 3,099 ms
コンパイル使用メモリ 185,932 KB
実行使用メモリ 37,856 KB
最終ジャッジ日時 2025-10-25 16:59:31
合計ジャッジ時間 31,871 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19 WA * 3
権限があれば一括ダウンロードができます

ソースコード

diff # 

//半分全列挙
#include <iostream>
#include <algorithm>
#include <atcoder/all>
#include <tuple>
#include <map>
using namespace std;
using namespace atcoder;
using ll = long long;
//#define endl "\n";
ll Q;
vector<pair<int,int>> v;

vector<int> nn = {1, 8};
void dfs(int val, int pos, int num){
  if(pos == 8){
    v.push_back({val, num});
    return;
  }
  for(int i = 0; i < 2; i++){
    for(int j = 1; j <= 3; j++){
      if(val * 10 + nn[i]*j > 81181819) continue;
      dfs(val * 10 + nn[i]*j, pos + 1, max(num, j));
    }
  }
  dfs(val * 10, pos + 1, num);
}

void calc(int tar, int num, int st, vector<ll> &ret){
  vector<ll> vv;
  while(tar > 0){
    vv.push_back(tar % 10);
    tar /= 10;
  }
  int kakeru10 = 1;
  //num<=3だから一意に決まる
  for(int i = 0; i < (int)vv.size(); i++){
    if(i != 0) kakeru10 *= 10;
    if(vv[i] < 0){
      vv[i + 1] -= 1;
      vv[i] += 10;
    }
    if(vv[i] == 0) continue;
    if(vv[i] == 1){
      ret[st] += kakeru10;
      continue;
    }
    if(vv[i] == 2){
      ret[st] += kakeru10;
      ret[st + 1] += kakeru10;
      continue;
    }
    if(vv[i] == 3){
      ret[st] += kakeru10;
      ret[st + 1] += kakeru10;
      ret[st + 2] += kakeru10;
      continue;
    }
    if(vv[i] == 4){
      ret[st] += kakeru10 * 8;
      ret[st + 1] += kakeru10 * 8;
      ret[st + 2] += kakeru10 * 8;
      vv[i + 1] -= 2;
      continue;
    }
    if(vv[i] == 6){
      ret[st] += kakeru10 * 8;
      ret[st + 1] += kakeru10 * 8;
      vv[i + 1] -= 1;
      continue;
    }
    if(vv[i] == 7){
      ret[st] += kakeru10 * 8;
      ret[st + 1] += kakeru10 * 8;
      ret[st + 2] += kakeru10;
      vv[i + 1] -= 1;
      continue;
    }
    if(vv[i] == 8){
      ret[st] += kakeru10 * 8;
      continue;
    }
    if(vv[i] == 9){
      ret[st] += kakeru10 * 8;
      ret[st + 1] += kakeru10;
      continue;
    }
  }
}

int main(){
  cin >> Q;
  //vの生成
  dfs(0, 0, 0);
  sort(v.begin(), v.end());
  for(int q = 1; q <= Q; q++){
    ll N;
    cin >> N;
    int tar = 81181819 - N;
    int ret = 7;
    int idx1 = 0, idx2 = 0;
    for(int i = 0; i < (int)v.size(); i++){
      auto [val, num] = v[i];
      pair<int,int> p = {tar - val, -1};
      int pos = lower_bound(v.begin(), v.end(), p) - v.begin();
      if(val + v[pos].first == tar){
        if(num + v[pos].second < ret){
          ret = min(ret, num + v[pos].second);
          idx1 = i, idx2 = pos;
        }
      }
    }
    if(ret == 7){
      vector<ll> ans(7, 0);
      vector<ll> vv;
      int kakeru10 = 1;
      while(tar > 0){
        vv.push_back(tar % 10);
        tar /= 10;
        kakeru10 *= 10;
      }
      for(int i = 0; i < (int)vv.size(); i++){
        kakeru10 /= 10;
        int pos = 0;
        if(vv[i] >= 8){
          ans[pos] += kakeru10 * 8;
          pos++;
          vv[i] -= 8;
        }
        for(int j = 0; j < vv[i]; j++) ans[pos + j] += kakeru10;
      }
      cout << ans.size() << endl;
      for(auto p: ans) cout << p << endl;
    }else{
      vector<ll> ans(ret, 0);
      calc(v[idx1].first, v[idx1].second, 0, ans);
      calc(v[idx2].first, v[idx2].second, v[idx1].second, ans);
      cout << ans.size() << endl;
      for(auto p: ans) cout << p << endl;
    }
  }
  return 0;
}
0