結果

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

ソースコード

diff # 

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

int m=7;
vector<vector<int>> cand(m+1);
vector<vector<vector<int>>> vec(m+1,vector<vector<int>>(100));
void solve(){
  using ll=long long;
  ll n;
  cin>>n;
  string s=to_string(81181819-n);
  reverse(s.begin(),s.end());
  int k=10;
  while (s.size()<k) s+="0";
  vector<vector<bool>> dp(k+1,vector<bool>(10));
  vector prev(k+1,vector<pair<int,int>>(10));
  dp[0][0]=true;
  prev[0][0]={-1,-1};
  for (int a=0;a<=m;a++){
    for (int i=0;i<k;i++){
      for (int j=0;j<10;j++){
        if (!dp[i][j]) continue;
        for (int c:cand[a]){
          if ((j+c)%10!=s[i]-'0') continue;
          dp[i+1][(j+c)/10]=true;
          prev[i+1][(j+c)/10]={j,c};
        }
      }
    }
    if (dp[k][0]){
      cout<<a<<endl;
      vector<ll> ans(a);
      ll now=0;
      ll pw=1;
      for (int i=0;i<k;i++) pw*=10;
      for (int i=k;i>0;i--){
        pw/=10;
        auto p=prev[i][now];
        now=p.first;
        for (int j=0;j<a;j++){
          ans[j]+=pw*vec[a][p.second][j];
        }
      }
      for (int i=0;i<a;i++) cout<<ans[i]<<endl;
      return;
    }
  }
}

int main(){
  vector<int> mem;
  auto dfs=[&](auto dfs,int v,int k=0){
    cand[k].push_back(v);
    vec[k][v]=mem;
    if (k==m) return;
    for (int i:{0,1,8}){
      mem.push_back(i);
      dfs(dfs,v+i,k+1);
      mem.pop_back();
    }
  };
  dfs(dfs,0);
  for (int i=0;i<=m;i++) cand[i].erase(unique(cand[i].begin(),cand[i].end()),cand[i].end());
  int t;
  cin>>t;
  while (t--) solve();
}

/*
using ll=long long;
ll m=81181819+10;
ll inf=1e9;
vector<ll> vec;
vector<ll> d(m,inf);
void solve(){
  ll n;
  cin>>n;
  cout<<d[n]<<endl;
}

int main(){
  auto dfs=[&](auto dfs,ll v){
    if (v) vec.push_back(v);
    if (v>=m) return;
    for (int u:{0,1,8}){
      if (v==0&&u==0) continue;
      dfs(dfs,v*10+u);
    }
  };
  dfs(dfs,0);
  sort(vec.begin(),vec.end());
  queue<int> q;
  d[0]=0;
  q.push(0);
  while (!q.empty()){
    int v=q.front();
    q.pop();
    for (int u:vec){
      int nv=v+u;
      if (nv>=m) break;
      if (d[nv]!=inf) continue;
      d[nv]=d[v]+1;
      q.push(nv);
    }
  }
  int t;
  cin>>t;
  while (t--) solve();
}
*/
0