fork(2) download 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. using namespace std;
  5.  
  6. const int INF = 1e9;
  7.  
  8. int n,tests;
  9. int dist[1<<20],best[1<<20],code[1024][1024];
  10. int restore_sum[1<<20],restore_remainder[1<<20];
  11. int cnt;
  12. queue <int> q;
  13. vector <int> v[1<<20];
  14.  
  15. void build_graph() {
  16.   int i,j,z,next_sum,next_remainder;
  17.  
  18.   cnt=0;
  19.   for(i=0;i<=n;i++) for(j=0;j<n;j++) {
  20.     code[i][j]=++cnt;
  21.     restore_sum[code[i][j]]=i;
  22.     restore_remainder[code[i][j]]=j;
  23.   }
  24.  
  25.   for(i=1;i<=cnt;i++) v[i].clear();
  26.  
  27.   for(i=0;i<=n;i++) for(j=0;j<n;j++) {
  28.     for(z=0;z<=9;z++) {
  29.       next_sum=i+z;
  30.       next_remainder=j*10+z;
  31.       next_remainder%=n;
  32.       if((next_sum==i && next_remainder==j) || next_sum>n) continue;
  33.       v[code[next_sum][next_remainder]].push_back(code[i][j]);
  34.     }
  35.   }
  36. }
  37.  
  38. void bfs() {
  39.   int i,curr,current_distance;
  40.  
  41.   while(!q.empty()) q.pop();
  42.   for(i=1;i<=cnt;i++) dist[i]=INF;
  43.   dist[code[n][0]]=0;
  44.  
  45.   q.push(code[n][0]);
  46.  
  47.   while(!q.empty()) {
  48.     curr=q.front();
  49.     q.pop();
  50.  
  51.     for(i=0;i<v[curr].size();i++) {
  52.       current_distance=dist[curr]+1;
  53.       if(dist[v[curr][i]]>current_distance) {
  54.         dist[v[curr][i]]=current_distance;
  55.         best[v[curr][i]]=restore_sum[curr]-restore_sum[v[curr][i]];
  56.         q.push(v[curr][i]);
  57.       }
  58.       else if(dist[v[curr][i]]==current_distance) {
  59.         best[v[curr][i]]=min(best[v[curr][i]],restore_sum[curr]-restore_sum[v[curr][i]]);
  60.       }
  61.     }
  62.   }
  63. }
  64.  
  65. int main() {
  66.   //ios_base::sync_with_stdio(false);
  67.   //cin.tie(NULL);
  68.   //freopen("test.txt","r",stdin);
  69.   int tests,sum,remainder,p;
  70.  
  71.   scanf("%d", &tests);
  72.   while(tests--) {
  73.     scanf("%d", &n);
  74.     build_graph();
  75.     bfs();
  76.     sum=0;
  77.     remainder=0;
  78.     while(sum<n || remainder!=0) {
  79.       p=best[code[sum][remainder]];
  80.       printf("%d", p);
  81.       sum+=p;
  82.       remainder*=10;
  83.       remainder+=p;
  84.       remainder%=n;
  85.     }
  86.     printf("\n");
  87.   } 
  88.  
  89.   return 0;
  90. }
Runtime error #stdin #stdout 0.04s 36192KB
comments (?)
stdin 
Standard input is empty
stdout
https://ideone.com/6E3F3J
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!