SHARE
TWEET

Untitled

a guest Jul 19th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.                               _                             _        _____   __
  3.                              | |                           | |      | ____| / /
  4.                           ___| |__   __ _ _____      ____ _| |_ __ _| |__  / /_
  5.                          / __| '_ \ / _` / __\ \ /\ / / _` | __/ _` |___ \| '_ \
  6.                          \__ \ | | | (_| \__ \\ V  V / (_| | || (_| |___) | (_) |
  7.                          |___/_| |_|\__,_|___/ \_/\_/ \__,_|\__\__,_|____/ \___/
  8.  
  9. */
  10. #include <bits/stdc++.h>
  11. using namespace std;
  12. typedef long long ll;
  13. #define forl(i,k,n)  for(i = k; i < n; ++i)
  14. #define forg(i,k,n)  for(i = k; i >= n; --i)
  15. #define forle(i,k,n)  for(i = k; i <= n; ++i)
  16. #define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
  17. #define time__(d) for( auto blockTime = make_pair(chrono::high_resolution_clock::now(), true); blockTime.second; debug("%s: %lld ms\n", d, chrono::duration_cast<chrono::milliseconds>(chrono::high_resolution_clock::now() - blockTime.first).count()), blockTime.second = false)
  18. #define endl '\n'
  19. typedef unsigned long long ull;
  20. typedef long double ld;
  21. typedef pair <ull, ull> p;
  22. const int INF = (int) 1e9;
  23. inline ll countSetBit(ll i) { i = i - ((i >> 1) & 0x55555555); i = (i & 0x33333333) + ((i >> 2) & 0x33333333); i = (i + (i >> 4)) & 0x0f0f0f0f; i = i + (i >> 8); i = i + (i >> 16); return i & 0x3f; }
  24. inline void set_bit(ll &n, ll b) { n |= 1 << b; }
  25. inline void unset_bit(ll &n, ll b) { n &= ~(1 << b); }
  26. inline void toggle_bit(ll &n, ll b) { n ^= 1 << b; }
  27. inline void swap(ll &a, ll &b) { a ^= b; b ^= a; a ^= b; }
  28. inline int digitContain(ll a) { return (ll) (floor(log10(a)) + 1); }
  29. inline bool isPoweroftwo(ll x) { return x && (!(x&(x-1))); }
  30. inline ll ipow(ll base, ull exp) { ll result = 1; while (exp) { if (exp & 1) result *= base; exp >>= 1; if (!exp) break; base *= base; } return result; }
  31. inline ll msd(ll n) { return ipow(10, (long double) (log10(n) - floor(log10(n)))); }
  32. inline void fast_io() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); }
  33. void solve();
  34.  
  35. int main()
  36. {
  37.     fast_io();
  38.     time__("Runtime") {
  39.         solve();
  40.     }
  41.     return 0;
  42. }
  43.  
  44. map <p, p> dp;  //map of pair of pairs / points
  45.  
  46. p dfs(p in)
  47. {
  48.     ull cur = 1, res;
  49.     if(in.second < 10)
  50.         return make_pair(in.first || in.second, in.second - max(in.first, in.second));
  51.     if(dp.find(in) != dp.end())
  52.         return dp[in];
  53.     while (cur <= in.second / 10)
  54.         cur *= 10;
  55.     p mi = dfs(make_pair(max(in.first, in.second / cur), in.second % cur));
  56.     res = mi.first;
  57.     mi = dfs(make_pair(in.first, in.second / cur * cur + mi.second));
  58.     return dp[in] = make_pair(mi.first + res, mi.second);
  59. }
  60.  
  61. void solve()
  62. {
  63.     ull x;
  64.     cin >> x;
  65.     cout << dfs(make_pair(0, x)).first << endl;
  66. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top