fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. #include <cstring>
  6.  
  7. using namespace std;
  8.  
  9. #define POS     10
  10. #define TIGHT   2
  11. #define NUM_369 10
  12.  
  13. int dp[POS][TIGHT][NUM_369];
  14.  
  15. vector<int> NumToDigits(int n) 
  16. {
  17.     vector<int> digits;
  18.     while (n > 0) 
  19.     {
  20.         digits.push_back(n % 10);
  21.         n /= 10;
  22.     }
  23.     reverse(digits.begin(), digits.end());
  24.     return digits;
  25. }
  26.  
  27. // Digit DP function
  28. int DigitDP(const vector<int>& digits, int pos, bool tight, int count) 
  29. {
  30.     if (pos == digits.size()) 
  31.         return count;
  32.  
  33.     if (dp[pos][tight][count] != -1)
  34.         return dp[pos][tight][count];
  35.  
  36.     int limit = tight ? digits[pos] : 9;
  37.     int total = 0;
  38.  
  39.     for (int i = 0; i <= limit; ++i) 
  40.     {
  41.         int currentCount = count;
  42.         if (i == 3 || i == 6 || i == 9)
  43.             ++currentCount;
  44.         total += DigitDP(digits, pos + 1, tight && (i == limit), currentCount);
  45.     }
  46.  
  47.     dp[pos][tight][count] = total;  // save data to avoid re-calculate
  48.     return total;
  49. }
  50.  
  51. // Count total 3-6-9 digits from 1 to n
  52. int CountClaps(int n) 
  53. {
  54.     if (n <= 0) 
  55.         return 0;
  56.     vector<int> digits = NumToDigits(n);
  57.     memset(dp, -1, sizeof(dp));
  58.     return DigitDP(digits, 0, true, 0);
  59. }
  60.  
  61. int main()
  62. {
  63.     int a, b;
  64.     cin >> a >> b;
  65.  
  66.     if (a < 1 || b > 100000000)
  67.         return -1;
  68.  
  69.     if (b < a)
  70.         swap(a, b);
  71.  
  72.     cout << CountClaps(b) - CountClaps(a - 1) << endl;
  73.     return 0;
  74. }
  75.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
999999 10000000
stdout
copy 
19200006
https://ideone.com/VvGP5g
language:
C++14 (gcc 8.3)
created:
11 hours 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!