結果

問題 No.3316 Make 81181819 with only 0,1,or 8
コンテスト
ユーザー のらら
提出日時 2025-09-17 23:17:32
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 3,273 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 3,317 ms
コンパイル使用メモリ 185,972 KB
実行使用メモリ 529,760 KB
最終ジャッジ日時 2025-10-25 17:00:48
合計ジャッジ時間 101,095 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1
other MLE * 22
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

//半分全列挙
//もう少し高速化したい
#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 <= 3; i++){
    for(int j = 0; j <= 3 - i; j++){
      if(val * 10 + i + 8*j <= 81181819) dfs(val * 10 + i + 8*j, pos + 1, max(num, i + j));
    }
  }
}

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());
  cout << v.size() << endl;
  for(int q = 1; q <= Q; q++){
    ll N;
    cin >> N;
    int tar = 81181819 - N;
    int ret = 7;
    int idx1 = 0, idx2 = 0;
    int pos = (int)v.size() - 1;
    for(int i = 0; i < (int)v.size(); i++){
      auto [val, num] = v[i];
      if(tar - val < val) break;
      while(v[pos].first >= tar - val){
        if(v[pos].first == tar - val && num + v[pos].second < ret){
          ret = min(ret, num + v[pos].second);
          idx1 = i, idx2 = pos;
        }
        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