fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. vector <int> digit;
  7. int n;
  8. ll dp[20][20][2][2];
  9.  
  10. ll calc(int id, int cnt, bool tight, bool out) {
  11.     if (id == n) return (cnt <= 3 && out);
  12.     if (!tight && dp[id][cnt][tight][out] != -1) return dp[id][cnt][tight][out];
  13.  
  14.     ll ans = 0;
  15.     int lim = (tight ? digit[id] : 9);
  16.  
  17.     for (int i = 0; i <= lim; ++i) {
  18.         if (i == 0) ans += calc(id + 1, cnt, (tight && i == lim), (out | 0));
  19.         else ans += calc(id + 1, cnt + 1, (tight && i == lim), 1);
  20.     }
  21.  
  22.     if (!tight) dp[id][cnt][tight][out] = ans;
  23.     return ans;
  24. }
  25.  
  26. ll tinh(ll x) {
  27.     digit.clear();
  28.     while (x) {
  29.         digit.push_back(x % 10);
  30.         x /= 10;
  31.     }
  32.  
  33.     n = (int) digit.size();
  34.     reverse(digit.begin(), digit.end());
  35.     memset(dp, -1, sizeof dp);
  36.     return calc(0, 0, 1, 0);
  37. }
  38.  
  39. int main() {
  40.     ios_base::sync_with_stdio(0);
  41.     cin.tie(0); cout.tie(0);
  42.  
  43.  
  44.     int t; cin >> t;
  45.     while (t--) {
  46.         ll a, b; cin >> a >> b;
  47.         if (a > 1) cout << tinh(b) - tinh(a - 1) << '\n';
  48.         else cout << tinh(b) << '\n';
  49.     }
  50.  
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/uWjamx
language:
C++14 (clang 8.0)
created:
5 hours 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!