fork download 
  1. #include "bits/stdc++.h"
  2. #define PRECISION(x) cout << fixed << setprecision(x)
  3. #define FAST_IO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  4. #define SZ(X) ((int)(X).size())
  5. #define ALL(X) (X).begin(), (X).end()
  6. #define ALLR(X) (X).rbegin(), (X).rend()
  7. #define MP make_pair
  8. #define PB push_back
  9. #define EB emplace_back
  10. #define F first
  11. #define S second
  12.  
  13. using namespace std;
  14.  
  15. template<class T> bool max_self(T & a, const T & b){ 
  16.   return b > a ? a = b, true : false; 
  17. }
  18. template<class T> bool min_self(T & a, const T & b){ 
  19.   return b < a ? a = b, true : false;    
  20. }
  21. typedef long long LL;
  22. const int INF = 1e9 + 7;
  23. const double PI = acos(-1.0);
  24. const double EPS = (1e-9);
  25.  
  26. const int nax = 1e5 + 5;
  27. int f, t, x, dp[nax][2];
  28. string from, to;
  29.  
  30. int util(string a){
  31.   int N = SZ(a);
  32.   memset(dp, 0, sizeof dp);
  33.  
  34.   for(int idx = N - 1, lim; idx >= 0; --idx){
  35.     lim = a[idx] - '0';
  36.     for(int d = 0; d <= 9; ++d){
  37.       dp[idx][0] += dp[idx + 1][0];
  38.       if(d == x) dp[idx][0] += pow(10, N - 1 - idx);
  39.     }
  40.  
  41.     for(int d = 0; d <= lim; ++d){
  42.       dp[idx][1] += dp[idx + 1][d == lim];
  43.       if(d == x){
  44.         string rest = a.substr(idx + 1);
  45.         if(d == lim && idx < N - 1) dp[idx][1] += stoi(rest) + 1;
  46.         else dp[idx][1] += pow(10, N - 1 - idx);
  47.       }
  48.     }
  49.   }
  50.  
  51.   return dp[0][1];
  52. }
  53.  
  54. int main(){
  55.   FAST_IO
  56.   cin >> f >> t >> x;
  57.   from = to_string(f - 1), to = to_string(t);
  58.  
  59.   cout << util(to) - util(from);
  60.   return 0;
  61. }
  62.  
  63.  
Success #stdin #stdout 0s 4584KB
comments (?)
stdin 
1 22 2
stdout 
6
https://ideone.com/stlsCM
language:
C++14 (gcc 8.3)
created:
4 years 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!