fork download
copy 
  1. #include <iostream>
  2. #include <bits/stdc++.h> 
  3. typedef long long ll;
  4.  
  5. using namespace std;
  6. string k; 
  7. vector<int> v; 
  8. int d; 
  9. int n = 18; 
  10. ll M = 1e9 + 7; 
  11. const int N = 1e4 + 5; 
  12. const int D = 5; 
  13. ll dp[N][D][2] ; 
  14. void getdig(ll x){
  15.      k = ""; 
  16.      for(int i = n ; i>=0; i--){
  17. ll p = pow(10ll,i); 
  18.           ll a = x/p;
  19.           char c = a + '0'; 
  20.          k += c; 
  21.          x = x%p; 
  22.      }
  23.  
  24. }
  25. ll solve(int i, int count, int can){
  26.  
  27.      if(i < 0 && count <= 3) return 1ll; 
  28.      else if(i < 0) return 0; 
  29.   if(~dp[i][count][can] && can) return dp[i][count][can] ;  
  30.  
  31.      ll ans = 0ll; 
  32.      int a =   k[n - i] - '0'; 
  33.  for(int dig = 0; dig <= ((can)?9:a) ; dig++){
  34.     int nc = count; 
  35.     if(nc < 4) nc += (dig > 0); 
  36.  ans += solve(i - 1, nc, can||(dig < a)); 
  37.    }
  38.    return dp[i][count][can] = ans; 
  39. }
  40.  
  41. int main() {
  42. 	ios_base::sync_with_stdio(false); 
  43.     cin.tie(NULL); cout.tie(NULL); 
  44.     memset(dp, - 1, sizeof(dp)); 
  45.     int t;cin>>t; 
  46.     while(t--){
  47.          ll l, r; cin>>l>>r; 
  48.          getdig(r);
  49.          ll ans = solve(18, 0,0); 
  50.          getdig(l -1ll); 
  51.          ans = ans - solve(18,0,0); 
  52.         cout<<ans<<endl; 
  53.     }
  54.  
  55. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
4
1 1000
1024 1024
65536 65536
999999 1000001
stdout
copy 
1000
1
0
2
https://ideone.com/RxLori
language:
C++ (gcc 8.3)
created:
3 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!