Advertisement
Guest User

Untitled

a guest
Jul 19th, 2019
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.68 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement