fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define inf 100000000
  6. #define maxn 1000000
  7.  
  8. #define pb push_back
  9.  
  10. vector<int> v1, v2, v3;
  11. int dp[maxn+100];
  12.  
  13. void solve1(int num)
  14. {
  15.     if(num==0)
  16.         return;
  17.     int i, curmin, cura, n;
  18.     curmin = inf;
  19.     for(i=0; v1[i]<=num; i++){
  20.         cura = 1+dp[num-v1[i]];
  21.         if(cura<curmin){
  22.             curmin = cura;
  23.             n = v1[i];
  24.         }
  25.     }
  26.     v3.pb(n);
  27.     solve1(num-n);
  28. }
  29.  
  30. int main()
  31. {
  32.  
  33.     int i, j, num;
  34.     v1.pb(1);
  35.     for(i=2; i<=6; i++){
  36.     	num = 1;
  37.     	for(j=0; j<i-1; j++)
  38.     		num*=10;
  39.         v2.clear();
  40.         for(j=0; j<v1.size(); j++){
  41.             v2.pb(num+v1[j]);
  42.         }
  43.         v1.pb(num);
  44.         for(j=0; j<v2.size(); j++)
  45.             v1.pb(v2[j]);
  46.     }
  47.     v1.pb(1000000);
  48.     sort(v1.begin(), v1.end());
  49.     dp[1] = 1;
  50.     for(i=2; i<=maxn; i++){
  51.     	dp[i] = inf;
  52.     	for(j=0; v1[j]<=i; j++){
  53.     		dp[i] = min(dp[i], (1+dp[i-v1[j]]));
  54.     	}
  55.     }
  56.     //cout << dp[2] << "\n";
  57.         scanf("%d", &num);
  58.         solve1(num);
  59.         printf("%d\n", v3.size());
  60.         for(i=0; i<v3.size(); i++)
  61.             printf("%d ", v3[i]);
  62.         printf("\n");
  63.     return 0;
  64. }
Runtime error #stdin #stdout 0.15s 7132KB
comments (?)
stdin
copy 
32
stdout
copy 
Standard output is empty
https://ideone.com/BFWvJn
language:
C++ (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!