#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)(v).size()
using ll = long long;
// dp[pos][a[pos - 2]][a[pos - 1]][tight]
// if it is not a palindrome then a[i] != a[i - 1] && a[i] != a[i - 2]
ll dp[20][11][11][2];
ll calc_dp(vector<int> num, int pos = 0, int ppre = 10, int pre = 10, bool tight = true){
if(pos == sz(num)) return (min(ppre, pre) < 10);
if(dp[pos][ppre][pre][tight] != -1) return dp[pos][ppre][pre][tight];
int lb = 0, ub = (tight) ? num[pos] : 9;
ll answer = 0;
for(int digit = lb; digit <= ub; digit++){
if(digit == pre || digit == ppre) continue;
if(!digit && min(ppre, pre) == 10) continue;
//cout << digit <<" " << (tight & (digit == ub)) << " " << pos <<" " << pre <<" " << ppre << "\n";
answer = answer + calc_dp(num, pos + 1, pre, digit, tight & (digit == ub));
}
if(min(ppre, pre) == 10) answer = answer + calc_dp(num, pos + 1, 10, 10, false);
return dp[pos][ppre][pre][tight] = answer;
}
ll calc(ll x){
if(x <= 0) return 0;
vector<int> num;
while(x){
num.push_back(x % 10);
x /= 10;
}
reverse(num.begin(), num.end());
memset(dp, -1, sizeof(dp));
return calc_dp(num);
}
void solve()
{
ll a,b; cin >> a >> b;
//cout << calc(a - 1) <<" " << calc(b) << "\n";
cout << calc(b) - calc(a - 1) << "\n";
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
#define name "InvMOD"
if(fopen(name".INP", "r")){
freopen(name".INP","r",stdin);
freopen(name".OUT","w",stdout);
}
int t = 1; //cin >> t;
while(t--) solve();
return 0;
}
Compilation message (stderr)
numbers.cpp: In function 'int main()':
numbers.cpp:63:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
63 | freopen(name".INP","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
numbers.cpp:64:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | freopen(name".OUT","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |