fork download
copy 
  1. // #include <iostream>
  2. // #include<vector>
  3. // #include <algorithm>
  4. #include <bits/stdc++.h>
  5. using namespace std;
  6.  
  7. const int M = 1'000'000'007;
  8. const int INF=1e9+5;
  9. // const long long INF = LLONG_MAX / 4;
  10.  
  11. // void addi(int& a,int b){
  12. //     a+=b;
  13. //     while (a>=M){
  14. //         a-=M;
  15. //     }
  16. // }
  17.  
  18.     // if say till i its a boring number so if ith pos is odd and i put odd
  19.     // at it (even case also) so i will pass on the boringness to i+1 otherwise
  20.     // i wont pass boringness further
  21.  
  22. int cnt(bool flag,int i,string rs){
  23.         long long x;
  24.         int n=rs.size();
  25.         if (flag){
  26.             string xs;
  27.             if (0 <= n-i+1 && n-i+1 < n){
  28.                 xs=rs.substr(n-i+1);
  29.             } 
  30.             else {
  31.                 xs="0";
  32.             }
  33.             x = stoi(xs)+1;
  34.             }
  35.  
  36.         else{
  37.             x = (pow(10, i-1)+0.1);
  38.  
  39.         }
  40.         return x;
  41.         }
  42. int f(long long r){
  43.     string rs = to_string(r);
  44.     int n=rs.size();
  45.     vector<vector<long long> >dp(n+1,vector<long long>(2,0));
  46.  
  47.     for(int i=1;i<=n;i++){
  48.         for(int tight=0;tight<2;tight++){
  49.             int ub = tight? (rs[n-i]-'0'):9;
  50.  
  51.  
  52.             for(int d=0;d<=ub;d++){
  53.                 dp[i][tight]+=(d*cnt(tight & (d==ub),i,rs)+dp[i-1][tight & (d==ub)]);
  54.             }
  55.  
  56. }
  57.    }
  58.     return dp[n][1];
  59. }
  60.  
  61.  
  62.  
  63.  
  64. int main() {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(nullptr);
  67.  
  68.     int t;
  69.     cin>>t;
  70.  
  71.     while(t>0){
  72.         long long x,y;
  73.         cin>> x>>y;
  74.  
  75.         long long ans= f(y)-f(x-1);
  76.  
  77.         cout<< ans<<endl;
  78.         t--;
  79.  
  80.     }
  81.     return 0;
  82. }
  83.  
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
3
0 10
28 31
0 99
stdout
copy 
46
28
900
https://ideone.com/YH9yOk
language:
C++ (gcc 8.3)
created:
11 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!