fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define ll long long
  7. #define ull unsigned long long
  8. #define f first
  9. #define ith_op second
  10. #define sort_all(v) sort(v.begin(), v.end())
  11.  
  12. #define ya_sayed_ya_badawy            \
  13.     ios_base::sync_with_stdio(false); \
  14.     cin.tie(NULL);
  15.  
  16. const int MAX = 4e5 + 50;
  17. const int MAX_N = 1e5 + 50;
  18. int MOD = 1e9 + 7;
  19. const int OO = 1e18;
  20. const double EPS = (double)1e-9;
  21.  
  22. int add(ll a, ll b)
  23. {
  24.     return ((a % MOD) + (b % MOD)) % MOD;
  25. }
  26.  
  27. int sub(ll a, ll b)
  28. {
  29.     return ((a % MOD) - (b % MOD) + MOD) % MOD;
  30. }
  31.  
  32. int mul(ll a, ll b)
  33. {
  34.     return ((a % MOD) * (b % MOD)) % MOD;
  35. }
  36.  
  37. int fp(ll base, ll pow)
  38. {
  39.     if (pow == 0)
  40.     {
  41.         return 1;
  42.     }
  43.  
  44.     ll res = fp(base, pow / 2);
  45.  
  46.     if (pow % 2 == 0)
  47.     {
  48.         return mul(res, res);
  49.     }
  50.  
  51.     return mul(base, mul(res, res));
  52. }
  53.  
  54. int inv(ll up, ll down)
  55. {
  56.     return mul(up, fp(down, MOD - 2));
  57. }
  58.  
  59. string l, r;
  60.  
  61. int dp(int idx, bool exceeded_lower, bool below_upper, bool started, string res = "")
  62. {
  63.  
  64.     if (idx == (int)l.size())
  65.     {
  66.         return 1;
  67.     }
  68.  
  69.     int start = (exceeded_lower) ? 0 : l[idx];
  70.     int end = (below_upper) ? 9 : r[idx];
  71.  
  72.     int ret = 0;
  73.  
  74.     for (char i = start; i <= end; i++)
  75.     {
  76.  
  77.         bool new_exceed_lower = exceeded_lower || (i > l[idx]);
  78.         bool new_below_lower = below_upper || (i < r[idx]);
  79.         bool new_started = started || (i != '0');
  80.  
  81.         ret += dp(idx + 1, new_exceed_lower, new_below_lower, new_started);
  82.     }
  83.  
  84.     return ret;
  85. }
  86.  
  87. string normalize_length(string s, int len)
  88. {
  89.     return (string(len - (int)s.size(), '0') + s);
  90. }
  91.  
  92. void solve()
  93. {
  94.  
  95.     cin >> l >> r;
  96.  
  97.     int max_len = max(l.size(), r.size());
  98.     l = normalize_length(l, max_len);
  99.     r = normalize_length(r, max_len);
  100.  
  101.     cout << dp(0, 0, 0, 0);
  102. }
  103.  
  104. signed main()
  105. {
  106.     ya_sayed_ya_badawy int t = 1;
  107.  
  108.     cin >> t;
  109.  
  110.     while (t--)
  111.     {
  112.         solve();
  113.         if (t != 0)
  114.         {
  115.             cout << endl;
  116.         }
  117.     }
  118.     return 0;
  119. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/qgECfc
language:
C++14 (gcc 8.3)
created:
3 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!