fork download
copy 
  1. ///0-0 : what is your motivation, quan606303?
  2. ///quan606303 : Hutao
  3. /*idea : 
  4.  
  5.  
  6.  
  7. */
  8. #include <bits/stdc++.h>
  9. #define int long long
  10. #define ll long long
  11. #define INTMAX INT_MAX
  12. #define INTMIN INT_MIN
  13. #define LONGMAX LLONG_MAX
  14. #define LONGMIN LLONG_MIN
  15. #define fi first
  16. #define se second
  17. #define memfull(a,b) memset(a,b,sizeof(a));
  18. #define endl '\n'
  19. #define file(a) freopen(a".inp","r",stdin); freopen(a".out","w",stdout);
  20. using namespace std;
  21. const int MOD=1e9+7;
  22. const int maxn=1e6+7;
  23. int n;
  24. int max_num(int x)
  25. {
  26.     int maxx=0;
  27.     while (x!=0)
  28.     {
  29.         maxx=max(maxx,x%10);
  30.         x/=10;
  31.     }
  32.     return maxx;
  33. }
  34. int len(int x)
  35. {
  36.     int cnt=0;
  37.     while (x!=0)
  38.     {
  39.         x/=10;
  40.         cnt++;
  41.     }
  42.     return cnt;
  43. }
  44. void sub1()
  45. {
  46.     int ans=0;
  47.     while (n!=0)
  48.     {
  49.         ans++;
  50.         n-=max_num(n);
  51.     }
  52.     cout<<ans;
  53. }
  54. pair<int,int> dp[10][maxn];
  55. int p[15];
  56. void sub2()
  57. {
  58.     for (int digit=0;digit<=9;digit++)
  59.     {
  60.         for (int i=0;i<maxn;i++)
  61.         {
  62.             int cnt=max(digit,max_num(i));
  63.             if (i-cnt<=0)dp[digit][i]={1,i-cnt};
  64.             else dp[digit][i]={dp[digit][i-cnt].fi+1,dp[digit][i-cnt].se};
  65.         }
  66.     }
  67.     int ans=0;
  68.     while (n!=0)
  69.     {
  70.         //cout<<n<<endl;
  71.         int cnt=n;
  72.         int left=cnt%1000000;
  73.         int right=cnt/1000000;
  74.         int tam=max_num(right);
  75.          pair<int,int> cnt2=dp[tam][left];
  76.          //cout<<cnt2.fi<<" "<<cnt2.se<<" "<<tam<<" "<<left<<endl;
  77.         ans+=cnt2.fi;
  78.         cnt=right*1000000+cnt2.se;
  79.        n=cnt;
  80.     }
  81.     cout<<ans;
  82. }
  83. int32_t main()
  84. {
  85.     ios_base::sync_with_stdio(0);
  86.     cin.tie(0);
  87.     cout.tie(0);
  88.     file("DIGIT");
  89.     cin>>n;
  90.    sub2();
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0.2s 160052KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/k9lYLl
language:
C++14 (gcc 8.3)
created:
2 days 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!