fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define int long long
  3.  
  4. using namespace std;
  5.  
  6. const int N = 20;
  7. const int MOD = 1e9+ 7;
  8.  
  9. int a[N];
  10. int dp[N][N][10][2];
  11.  
  12. int d, l, k;
  13.  
  14. int call(int i, bool smaller, int last, int cnt, int ok) {
  15.  
  16.     // cout << i << " " << smaller << " " << last << " " << cnt << " " << ok << endl;
  17.  
  18.     if (i < 0) {
  19.  
  20.         return cnt <= k;
  21.  
  22.     }
  23.  
  24.     if (!smaller && dp[i][cnt][last][ok] != -1) return dp[i][cnt][last][ok];
  25.  
  26.     int res = 0;
  27.     int lim = smaller ? a[i] : 9;
  28.  
  29.     for (int k = 0; k <= lim; k++) {
  30.  
  31.         bool Ok = (k > 0) || ok;
  32.  
  33.         if (!Ok) res += call(i - 1, smaller && (k == lim), 0, 0, 0);
  34.  
  35.         else res += call(i - 1, smaller && (k == lim), k, cnt + (abs(k - last) <= d) * ok, 1);
  36.  
  37.     }
  38.  
  39.     return dp[i][cnt][last][ok] = res;
  40.  
  41. }
  42.  
  43. int g(int x) {
  44.  
  45.     memset(dp, -1, sizeof(dp));
  46.  
  47.     l = 0;
  48.  
  49.     while (x) {
  50.  
  51.         a[l++] = x % 10;
  52.         x /= 10;
  53.  
  54.     }
  55.  
  56.     return call(l - 1, 1, 0, 0, 0);
  57.  
  58. }
  59.  
  60. signed main() {
  61.  
  62.     int a, b;
  63.     cin >> a >> b >> d >> k;
  64.  
  65.     cout << g(b) - g(a- 1) << endl;
  66.  
  67. }
  68.  
Success #stdin #stdout 0.01s 5516KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9234883290459
https://ideone.com/HldjtL
language:
C++14 (gcc 8.3)
created:
326 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!