fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <cstdlib>
  7. #include <cassert>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <deque>
  12. #include <map>
  13. #include <unordered_map>
  14. #include <set>
  15. #include <unordered_set>
  16. #include <string>
  17. #include <algorithm>
  18. #include <utility>   
  19. #define int long long
  20. using namespace std;
  21.  
  22.  
  23.  
  24. int dp[20][2][12], n;
  25. string s;
  26.  
  27.  
  28. int countNumbers(int idx, int tight, int last){
  29.     if(idx == n) {
  30.        return 1;
  31.     }
  32.     int &ans = dp[idx][tight][last];
  33.     if(ans != -1)
  34.         return ans;
  35.  
  36.     ans = 0;
  37.  
  38.     int limit = tight ? (s[idx] - '0') : 9;
  39.  
  40.     if(last == 10){
  41.         for(int i = 0; i <= limit; i++){
  42.            ans += countNumbers(idx + 1, tight & (i == limit), i == 0 ? 10: i);
  43.         }
  44.     } else{
  45.     	for(int i = 0; i <= limit; i++){
  46.     	   if(i != last)
  47.     		 ans += countNumbers(idx + 1, tight & (i == limit), i);
  48.     	}
  49.     }
  50.  
  51.     return ans;
  52. }
  53.  int countNumbers(string low, string high) {
  54.          s = high;
  55.          n = s.size();
  56.          memset(dp, -1, sizeof(dp));
  57.          int ans = countNumbers(0, 1, 10); // 10 is flag for leading zero
  58.  
  59.          s = low;
  60.          n = s.size();
  61.          memset(dp, -1, sizeof(dp));
  62.          ans = ans - countNumbers(0, 1, 10);
  63.  
  64.          bool check_low = true;
  65.          for(int i = 1; i < low.size(); i++){
  66.              if(low[i] == low[i - 1])
  67.                 check_low = false;
  68.          }
  69.          if(check_low){
  70.              ans++;
  71.          }
  72.          return ans;
  73. }
  74.  
  75. int32_t main() {
  76.     ios_base::sync_with_stdio(false);
  77.     cin.tie(0);
  78.   #ifndef ONLINE_JUDGE
  79.     freopen("input.txt", "r", stdin);
  80.     freopen("output.txt", "w", stdout);
  81.   #endif
  82.  
  83.   string low, high;
  84.   cin >> low >> high;
  85.  
  86.  
  87.   cout << countNumbers(low, high);
  88.  
  89.  return 0;
  90. }
Success #stdin #stdout 0.01s 5440KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/pixt1P
language:
C++14 (gcc 8.3)
created:
278 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!