Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.16 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5.  
  6. ll s, l, k, dp[20], st[20];
  7.  
  8. void read() {
  9. cin >> s;
  10. }
  11.  
  12. ll slowve(ll n) {
  13. ll ans = 0;
  14. for (ll k = 1; k <= n; k++) {
  15. ll p = k;
  16. while (p) {
  17. if (p % 10 == 5) ans++;
  18. p /= 10;
  19. }
  20. }
  21. return ans;
  22. }
  23.  
  24. void upd(int i, ll &s, ll &l) {
  25. l += (s % 10) * st[i];
  26. s /= 10;
  27. }
  28.  
  29. ll solve(ll n) {
  30. s = n;
  31. dp[0] = st[0] = 1;
  32. for (int i = 1; i < 18; i++) {
  33. st[i] = st[i - 1] * 10;
  34. dp[i] = dp[i - 1] * 10 + st[i];
  35. }
  36. l = 0;
  37. k = s % 10 > 4;
  38. upd(0, s, l);
  39. for (int i = 1; s; i++) {
  40. k += dp[i - 1] * (s % 10);
  41. if (s % 10 == 5) k += l + 1;
  42. if (s % 10 > 5) k += st[i];
  43. upd(i, s, l);
  44. }
  45. // cout << k;
  46. return k;
  47. }
  48.  
  49. signed main() {
  50. ios_base::sync_with_stdio(0);
  51. cin.tie(0);
  52.  
  53. // for (ll i = 1; i < 1000; i++) {
  54. // if (slowve(i) != solve(i)) {
  55. // cout << i << endl;
  56. // cout << slowve(i) << ' ' << solve(i);
  57. // return 0 ;
  58. // }
  59. // }
  60. read();
  61. cout << solve(s);
  62. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement