fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string s;
  5. int K;
  6. long long dp[20][2][20][11][2][2];
  7. bool vis[20][2][20][11][2][2];
  8.  
  9. long long dfs(int pos, int tight, int cnt, int last, int found, int started) {
  10.     if (pos == (int)s.size())
  11.         return found;
  12.  
  13.     long long &res = dp[pos][tight][cnt][last][found][started];
  14.     if (vis[pos][tight][cnt][last][found][started]) return res;
  15.     vis[pos][tight][cnt][last][found][started] = true;
  16.     res = 0;
  17.  
  18.     int limit = tight ? (s[pos] - '0') : 9;
  19.  
  20.     for (int d = 0; d <= limit; d++) {
  21.         int ntight = tight && (d == limit);
  22.         int nstarted = started || (d != 0);
  23.         int ncnt = cnt, nfound = found;
  24.  
  25.         if (!nstarted) {
  26.             ncnt = 0;
  27.         } else {
  28.             if (started && d == last) ncnt = cnt + 1;
  29.             else ncnt = 1;
  30.             if (ncnt >= K) nfound = 1;
  31.         }
  32.  
  33.         res += dfs(pos + 1, ntight, ncnt, nstarted ? d : 10, nfound, nstarted);
  34.     }
  35.     return res;
  36. }
  37.  
  38. long long solve(long long n) {
  39.     if (n < 0) return 0;
  40.     s = to_string(n);
  41.     memset(vis, 0, sizeof(vis));
  42.     return dfs(0, 1, 0, 10, 0, 0);
  43. }
  44.  
  45. int main() {
  46.     ios::sync_with_stdio(false);
  47.     cin.tie(nullptr);
  48.     long long A, B;
  49.     cin >> A >> B >> K;
  50.     cout << solve(B) - solve(A - 1);
  51.     return 0;
  52. }
  53.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin 
Standard input is empty
stdout 
46800308179393
https://ideone.com/XNy5W9
language:
C++14 (gcc 8.3)
created:
83 days ago
visibility:
secret

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!