fork(1) download
  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
stdin
32
stdout
Standard output is empty