fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const unsigned long long MOD = 1e9 + 7;
  5. const int INF = (int)2e9 + 7;
  6. const long long LINF = (long long)1e18;
  7. const unsigned long long mod1 = 183453789;
  8. const unsigned long long mod2 = 1234567891;
  9. const int P1 = 337, P2 = 263;
  10.  
  11. template<typename T>
  12. T input(){
  13.     T ans = 0, m = 1; char c = ' ';
  14.     while (!((c >= '0' && c <= '9') || c == '-')) c = getchar();
  15.     if (c == '-') m = -1, c = getchar();
  16.     while (c >= '0' && c <= '9') ans = ans * 10 + (c - '0'), c = getchar();
  17.     return ans * m;
  18. }
  19.  
  20. string nextString(bool flag = false){
  21.     char ch; string ans = "";
  22.     do { ch = getchar(); } while(ch <= ' ');
  23.     while(1) {
  24.         ans += ch; ch = getchar();
  25.         if ( (!flag && ch <= ' ') || (flag && ch < ' ') ) break;
  26.     }
  27.     return ans;
  28. }
  29. char nextChar(){
  30.     char ch;
  31.     do {ch = getchar(); } while(ch <= ' ');
  32.     return ch;
  33. }
  34. void read(string& s){ s = nextString(); }
  35. void read(char& c){ c = nextChar(); }
  36. template<typename T> void read(T& a){ a = input<T>(); }
  37. template<typename T, typename... R> void read(T& a, R&... r){ read(a); read(r...); }
  38.  
  39. const int N = 1e5 + 10;
  40. int f[N];
  41.  
  42. int solve(const string& s){
  43.     if (s == "0") return 0;
  44.     int n = s.size();
  45.     int res = 0;
  46.     res += f[n - 1];
  47.     vector < string > vec;
  48.  
  49.     for (int s = 1; s <= 9; ++ s){
  50.         for (int d = 0; d < 10; ++ d){
  51.             string t;
  52.             t += char('0' + s);
  53.             for (int i = 1; i < n; ++ i){
  54.                 char nxt = ((t[i - 1] - '0') + d) % 10 + '0';
  55.                 t += nxt;
  56.             }
  57.             if (d > 0 && n == 1) continue;
  58.             vec.push_back(t);
  59.         }
  60.     }
  61.  
  62.     for (const auto& x: vec){
  63.         res += (x <= s);
  64.     }
  65.  
  66.     return res;
  67. }
  68.  
  69. int32_t main(){
  70.     ios_base::sync_with_stdio(0); cin.tie(0);
  71.     #ifdef LOCAL
  72.         freopen("in.txt", "r", stdin);
  73.         freopen("out.txt", "w", stdout);
  74.     #else
  75.         freopen("arithnumbers.in", "r", stdin);
  76.         freopen("arithnumbers.out", "w", stdout);
  77.     #endif
  78.  
  79.     f[0] = 0, f[1] = 9;
  80.     for (int i = 2; i < N; ++ i){
  81.         f[i] = f[i - 1] + 90;
  82.     }
  83.  
  84.     string l, r;
  85.     read(l, r);    
  86.  
  87.     auto decrease = [](string& s){
  88.         if (s == "1"){
  89.             s = "0";
  90.             return;
  91.         }
  92.         int n = s.size();
  93.         int ptr = n - 1;
  94.         while (s[ptr] == '0'){
  95.             s[ptr] = '9';
  96.             ptr --;
  97.         }
  98.         s[ptr] --;
  99.         if (s[0] == '0') s = s.substr(1);
  100.     };
  101.     decrease(l);
  102.     cout << solve(r) - solve(l);
  103. }
Time limit exceeded #stdin #stdout 5s 3848KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/YGiC2g
language:
C++14 (gcc 8.3)
created:
7 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!