fork download
copy 
  1. #include <bits/stdc++.h> 
  2.  
  3. using namespace std;  
  4.  
  5. typedef long long ll;  
  6. typedef pair<int, int> ii;  
  7.  
  8. const int INF = 1e9;  
  9. const ll LINF = 1e18;  
  10.  
  11. vector<int> digit;  
  12.  
  13. vector<int> getDigit(ll n) {
  14. 	vector<int> ans; 
  15. 	for (; n > 0; n /= 10) ans.push_back(n % 10); 
  16. 	return ans; 
  17. }
  18.  
  19. ll memo[16][2][10];
  20.  
  21. ll dp(int idx, bool smaller, int prev_digit) {
  22. 	if (idx == -1) return 1;  
  23.  
  24. 	ll& ans = memo[idx][smaller][prev_digit]; 
  25. 	if (ans != -1 && smaller) return ans; 
  26.  
  27. 	ans = 0;  
  28. 	int max_digit = (smaller) ? 9 : digit[idx]; 
  29. 	for (int i = 0; i <= max_digit; i++) {
  30. 		if (prev_digit == 1 && i == 3) continue;
  31. 		ans += dp(idx - 1, smaller | (i < digit[idx]), i); 
  32. 	}
  33.  
  34. 	return ans; 
  35. }
  36.  
  37. ll solve(ll n) {
  38. 	if (n < 0) return 0; 
  39. 	digit = getDigit(n); 
  40. 	return dp(digit.size() - 1, 0, 0); 
  41. }
  42.  
  43. int main() {
  44. 	ios::sync_with_stdio(false); 
  45. 	cin.tie(nullptr); 	
  46. 	ll A, B; 
  47. 	while (cin >> A >> B) { 
  48. 		memset(memo, -1, sizeof memo); 
  49. 		ll ans = solve(B) - solve(A - 1); 
  50. 		cout << ans << '\n'; 	
  51. 	}
  52. }
  53.  
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
1 13
stdout
copy 
12
https://ideone.com/EKjDL2
language:
C++14 (gcc 8.3)
created:
1 year 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!